ARC014 魂の還る場所
https://atcoder.jp/contests/arc014/tasks/arc014_3?lang=ja
解法
各ボールの色の偶奇性に着目すると、各色円筒に入れられるボールの数が奇数であれば、その色のボールは最後に最低1個は円筒の中に残る。
則ち、答えの自明な下界として、#{色c|円筒に入れられる色がcのボールは奇数個}が考えられる。
以下この答えを達成可能であることを示す。
以下のように状態A, B, C, Dを定める
状態A:円筒が空
状態B:円筒に1個のボールが入っている
状態C:円筒に2個のボールが入っている
状態D:円筒に3個のボールが入っており、この3個は異なる色であり、更に次に入るボールと同じ色が端に存在するか、もうボールは入らない
実は、操作中、円筒がこの4種類の状態のみを取るように出来る。
状態Aのとき
次のボールを入れれば状態B
状態Bのとき
次のボールが円筒の中のボールと打ち消し合えば状態Aへ遷移する。そうでないならば状態Cへ遷移する。
状態Cのとき
次のボールが既に円筒に入っている2つのボールのいずれかと同じ色なら、それと打ち消し合うように入れれば状態Bに遷移する
そうでないならば、更にもう1つ先のボールを見つつ適切な方から入れれば、状態Dに出来る。
状態Dのとき
状態Dの定義から、適切な方からボールを入れれば状態Cに出来る
以上より、操作中常に円筒を状態A,B,C,Dのいずれかに保つことが出来る。
以下、このように操作を行った際の最終状態を考える。
#{色c|円筒に入れられる色がcのボールは奇数個} = 0のとき
偶奇性に着目すると最終状態はAかCだが、Cになる為には同じ色のボールが円筒内に2つ存在する必要がある為、不適。よって、最終状態はA。
#{色c|円筒に入れられる色がcのボールは奇数個}=1のとき
偶奇性に着目すると最終状態はBかDだが、Dになる為には同じ色のボールが円筒内に2つ存在する必要がある為、不適。よって、最終状態はB。
#{色c|円筒に入れられる色がcのボールは奇数個}=2のとき
偶奇性とボールの個数に着目すると、最終状態はCであると分かる。
#{色c|円筒に入れられる色がcのボールは奇数個}=3のとき
偶奇性とボールの個数に着目すると、最終状態はDであると分かる。
そして、これらは全て前述の下界と一致する。
