- 考えたこと
- 複数の山から0または1個とるゲーム
- すべての山が1以下の時、手番の人は勝つ
- 2が1つだけある時、そこから取ると負ける
- その山以外の山に1があるなら、全部取って相手に回せば勝ち
- ないなら負け
- 2が2つだけある場合
- 取ってしまうと負けるので同様に
- その山以外の山に1があるなら、全部取って相手に回せば勝ち
- ないなら負け
- 取ってしまうと負けるので同様に
- 3がひとつだけある場合
- 他の山に1があるなら3を取ると負ける
- そろそろ自然言語では困難を感じるのでコードで検証したい
- 考えたこと2
- 逆に考える
- 逆の操作「aiから1個以上選んで1増やす」
- A: aiがすべて0の時、負け
- この状態から逆操作したものを考える
- B: aiが0か1の時、1のものを全部取ってAに帰着できるので勝ち
- この状態から逆操作したものを考える
- aiは0〜2になるが、もし2がなければBに含まれるので2は1個以上ある
- でもBが勝利状態だから相手はそこに遷移することを避けようとする
- 避けられない局面になった時だけ遷移する
- C: 2が1つだけある、Bにしか遷移できないので負け
- この状態から逆操作したものを考える
- 2か3が1つで、残りは0か1の場合
- D: 2が1つで残りが0か1の時、Cに遷移できるので勝ち
- そろそろよくわからなくなってきた
- ここまでをまとめると以下の属性が影響しそう
- 一番大きな数は何か
- それは1つか、それ以上か
- それ以外の数はあるか
- 一番大きな数がxで、1つで、それ以外の数がない時、xが奇数なら勝ち
- それ以外の数がある時、残りの部分が似た問題になる
- xが偶数なら「0になったら負け」なので同じゲーム
- 奇数の時は逆のゲーム
- それ以外の数がある時、残りの部分が似た問題になる
- 一番大きな数が複数ある時、1個残すか、全部削るか、1個だけ削るか…
- 考察が足りてない感じ
- 1個残して削って負け局面になるならやる、この局面は勝ち
- 勝ち局面になるならそれをなるべく避けようとするはず
- それがどういう手なのか
- 大きな数を全部削った時にどうなるのか
- あ、一番大きな数が複数あって、それ以外がない時、を考えるべきだったか
- 1がx個あるとき
- 1個残して削ると負け局面
- 全部取って勝つ
- 2がx個ある時
- 全部取ると相手勝ち局面なのでやらない
- 1個残して削ると、最大値が偶数で1つなので、残りの問題になる、1がx-1個あるので全部取って相手勝ち、これもやらない
- xが3以上なら2個残して削る、相手は上のどちらかしかできないので相手負け
- xが2なら自分が負け
- 3がx個ある時
- xが2なら全部削って勝ち
- xが3以上なら
- 1個残して削ると「2がx-1個」の問題になる
- 1がx個あるとき
- だいぶわかってきた
- 個数の多い順にソートしてトップが偶数が奇数か、同率一位が1種か2種かそれ以上か、によってトップを取り除いた問題の「0が勝ちか負けか」に帰着される
- ソートして線形に処理するだけなので間に合う
- しかしこの考察をコンテスト中にリアルタイムでできる気がしないし、人間がやってるから見落とし経路とかありそう
- リアルタイムでやるにはどうするのがいいのか。ソルバーを作って小さい問題を解いて、そこからパターン発見かなぁ
- 逆に考える
- 公式解説
- だいぶシンプルな形に帰着されてた
-
コンテスト中にこの結論にたどり着くには、(メモ化) 再帰により小さいケースを解くプログラムを書 いたり、N = 2 のケースを紙と鉛筆で解くことで実験して仮説を立てる方法もあります。
- まあそうなるのか〜
- 考えたこと3
- そもそもこの問題、各山からの取るか取らないかの意思決定が他の山に全く干渉しないので、まずそれぞれの山が部分問題であると考えた方が良かったのではないか？
- そもそも山一つの時に奇数が勝ちなのはこういう形だから
- 山二個の場合
- 負け状態を丸、丸に遷移可能な勝ち状態を四角、四角にしか遷移できない状態を丸にすると
- あー、なるほど、すべてが偶数である時に負け、という仮説が立てられる
- 状態遷移図を勝ち負けで塗る
- 1山ずつの部分問題の結合として考えた場合、すべてが0になれば負け
- 1手進めるか進めないかの選択肢がある
- 相手が1手進めた時にはこちらも同じことをすることによって偶奇を保つことができる
