DDCC2016 本戦 C - 01文字列 -
問題
解説
https://ddcc2016-final.contest.atcoder.jp/data/other/ddcc2016-final/editorial.pdf
考察
公式解説そのまま
NをTのサイズとすると、
操作1と操作2は合計で N 回行われることは明らか。
よって、操作1と操作2をそれぞれ何回行うか、そのとき操作3は何回する必要があるかが分かればよさそう。
まず、操作1と操作2をそれぞれ何回行うかというのは、文字列Tをどこで区切るかということである(前半部分と後半部分に分ける)
次に操作3は何回する必要があるかについて、
前半部分( l とする)、後半部分( r とする)それぞれについて考える必要がありそう。
r については以下のように求めることができる。 (公式解説より引用)
1. 次に末尾に追加したい文字が 1 である限り,操作 2 を行う
2. N 文字入力したならば終了.そうでなければ 3. へ
3. 操作 3 を行い,0 と 1 を置き換える
4. 次に末尾に追加したい文字が 0 である限り,操作 2 を行う
5. 操作 3 を行い,0 と 1 を置き換える
6. N 文字入力したならば終了.そうでなければ 1. へ
l についてもほぼ同じ方法で求めることができる。
操作 3 を行うタイミングを l の構成時と r の構成時で揃えると考えることでで操作 3 の回数を l と r の max に押さえることができる。
これだけだと O(N2) になってしまうので、もう少し工夫する必要がある。
上記の考察から操作3が行われるのは、隣り合う文字が異なる場合と先頭が1の場合と末尾が0の場合だけである。 よって、その数を累積和で求めておけばO(N)でこの問題を解くことができる。
ソースコード
signed main() { int A, B, C; cin >> A >> B >> C; string T; int N; cin >> T; N = T.size(); int cum_sum[200001] = {}; Rep(i, N-1) { cum_sum[i+1] = cum_sum[i]; if ( T[i] != T[i+1] ) cum_sum[i+1]++; } int ans = INF; Rep(i, N+1) { int a = i, b = N-i; int x = 0, y = 0; if ( i ) x = cum_sum[i-1]; if ( i < N ) y = cum_sum[N-1] - cum_sum[i]; if ( i && T[0] == '1' ) x++; if ( i < N && T[N-1] == '0' ) y++; int c = max(x, y); ans = min(ans, A*a+B*b+C*c); } cout << ans << endl; return 0; }
感想
操作3の操作回数を求める方法が分からなかったのがだめだった。
回数をO(1)で求められないかをまず考察するようにしたい。
累積和のインデックスとfor文内の操作のインデックスをうまいこと調整するのが少しめんどくさかった。