ARC014C
考えたこと
スタック的になってるから、端の色だけ覚えておくわけにはいかない、消えた後中の色が出てくるので。
ボールは最大50個、選択肢は2^50ある
消すことができる時に必ず消して良いのかどうか
消して良いことを証明できたら楽
消せないとき、左右と今の色の3色のうち次に来る色と同じものが露出するように入れれば次で必ず消せる
この方法で、長さが2であれば次は1か3であり、その3は次で必ず2になる
短い配列に関して力づくで解いて問題なさそうか確認する
2^21くらいなら間に合いそう
公式解説
上記手順で常時3個以下を維持できる
終局までそれが維持できるので複雑な状態を経由する必要がない
下界に一致するから最適解というロジック
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]