ABC083 D - Wide Flip
解法
パズルっぽい問題です。
結局、"11111..."のように、最後を全て1にそろえた場合でも、区間の端から端を選択して操作すると0000...にすることができます。ので、結局は01や10のように、0と1が途中でひっくり返っている部分を消していくことを考える必要があります。
では、それぞれの0と1の区切れめをどう消すのが最適か、を考えてみると、
A01B(A,Bは任意の文字列)
の区切れめを消すには、"A0"という文字列に対して操作を行うか、"1B"という文字列に対して操作を行えばよさそうです。
ので、結局は"A0"の文字の長さと、"1B"の文字列の長さうち、より長い方を反転させればよいです。
あとはこれを繰り返せばよいので、最終的に求める値は以下のようになります。
- 01もしくは10という区切れ目に対して、その区切れ目の左右の文字数のうち大きい方の値をすべての区切れ目に対し計算し、その最小値をとったもの
あとはこれを計算することで、答えを求めることができます。
感想
最初は、111や000のような文字列をどうひっくりかえしていくか、を考えていたのですが、結局は01や10の区切れ目を消せばいい、ということに気づいてからは一瞬でした。
このようなパズルっぽい問題は、一回ハマると抜け出せなさそうなのでつらいです、今回も結構時間がかかってしまいましたが、なんとか解けたのでよかったです。
