B. Reverse Binary Strings
B問題がまったくわからず、ドツボにハマっていたアカウントがこちらです。
結局カンかつ未証明で通したけど、解説みるまでまったく見えてなかった。
たとえば「11101000」にたいして「10101010」あるいは「01010101」のどちらに変換するかを両方試して、反転の操作を最小化しよう、と考えると袋小路にはまる。
そうではなく、「0101...」に変換したいってことは連続する「00」または「11」を解消すると考える。
気づき
- x010101x を反転しても間の「010101」は「101010」となって、交互になる特性は壊れない
この気付きから、「11...00」または「00...11」をみつけて反転すれば「00」「11」を解消できる。
さらに両端と「00」または「11」を反転することでも「00」「11」を解消できる。
すべての「00」「11」を解消できれば全体は交互になっているはず。
よって、与えられた配列の「00」の個数と「11」の個数の最大値が、求める最小手数となる。
（「00」と「11」をペアにして解消する。一つ余るなら端とペアにして解消する）
気づけんよ……
