- 問題
https://codeforces.com/contest/1437/problem/B
- 解法
0と1をalternatingにするので以下のどちらかの形になります。
0101010…
1010101…
ここで、与えられた文字列について実際にリバースさせながら、操作回数を数える必要がない(問題で要求されていない)ので、より全体的な性質から答えが導けるのではないかと頭に入れておく必要があります。
手元で文字列の操作を幾らか実験すると、コードが著しく煩雑になりそうなので、さっき言った方法で問題を捉え直しましょう。
大事な観察としては、1の連続している数と0の連続している数はほとんどの場合で一致します。これは1と0の数が等しいことに加えて、1110101…と続いた場合、どこかで0の不足を補うことになるのですが、それは0が連続した場合にしか出来ないからです。
例外は0…01…10..0などの場合です。この場合、0は1よりも1回だけ連続している部分が少ないです。(ここで言う連続とは111の場合2回という意味です)
そして、1回の操作で1が連続している部分1箇所と、0が連続している部分1箇所を直すことができます。なぜなら、例えば111010…1010001…などと連続している所があったとします。1と0が交互に並んでいる場所から部分文字列を選んで反転させたとしても、1010…11101001…となり、無駄な操作になります。よって例の場合は、0が連続し始める部分を右端に選んで操作を行うと、1010…1011001…となって、0が連続する所と1が連続する場所をそれぞれ1つずつ減らすことができます。
以上の議論により、0と1のうち連続する所が何箇所あるかを数える問題に帰着されました。
提出コードは_SSRSさんのコードを見ながら書きました。
Sooh31's programming diary 