AtCoder Regular Contest 138 振り返り

AtCoder Regular Contest 138に参加しました。

結果

B問題のみAC。緑まであと少し！

 B - 01 Generation

問題概要

空の数列xに対して以下の操作を任意の順番で行い、指定された数列を作れるか？

• 操作A：xの要素すべてをflip(1なら0、0なら1に）した後、先頭に0をつける
• 操作B：xの末尾に0をつける

作れるかどうかをYes/Noで回答する。

考察

空の数列に対してA/Bどちらの操作を行っても[0]になるので、[0]から始めると考えます。

操作Aのみ行った場合、数列は次のように変化していきます。

0 → 01 → 010 → 0101 → 01010 → 010101

次に操作A/B両方行った場合を考えます。

操作Bは最初の0よりも右側にしか影響しないので、最初の0より左側は、操作Aのみ行った場合と同様、先頭が0で、以降1/0が交互に並びます。

具体例として数列 0100110 で考えていきます。

前述のとおり、左端から0/1が交互に並んでいる部分は操作Aで作ることができます。

この例では、左から3個、010の部分が操作Aで作れます。数列[0]から始めると考えると、2回の操作Aで010を作れます。操作Aが3回以上行われた場合は010...がより長く続くはずなので、操作Aは2回までしか行われていません。

次に、残りの0110の部分を操作A/Bで作れるかどうか考えます。

• 各数字は、その位置に0が追加されて以降にflipされた回数（=操作Aの回数）の偶奇を意味しています。
• 数字は左から右に向かって追加されていくので、各数字のflip回数は右隣の数字のflip回数より多いか同じになります。

以上の条件を満たすように各数字のflip回数を決定し、最低限必要なflip回数が操作Aの回数（2回）以下であれば、数列0100110を作ることができます。

右端の数字は、数字が0ならflip回数0、1なら1です。

右端から左へ辿っていくと、数字(0/1)が変化する部分でflip回数が1増えることになります。

この例では、0110の部分を作るのに最低限2回のflip(操作A)が必要ということがわかります。

010の部分は2回のA操作で作れるので、0100110は操作A/Bで作ることができます。