- 考えたこと
- スタック的になってるから、端の色だけ覚えておくわけにはいかない、消えた後中の色が出てくるので。
- ボールは最大50個、選択肢は2^50ある
- 消すことができる時に必ず消して良いのかどうか
- 消して良いことを証明できたら楽
- 消せないとき、左右と今の色の3色のうち次に来る色と同じものが露出するように入れれば次で必ず消せる
- この方法で、長さが2であれば次は1か3であり、その3は次で必ず2になる
- 短い配列に関して力づくで解いて問題なさそうか確認する
- 2^21くらいなら間に合いそう
- 公式解説
- ない、ユーザ解説がある https://kort0n.hatenablog.com/entry/2020/01/08/002039
- 上記手順で常時3個以下を維持できる
- 終局までそれが維持できるので複雑な状態を経由する必要がない
- 下界に一致するから最適解というロジック