caddi2018_b

https://gyazo.com/cb838b2af7700f03a0a0700e26823b26

https://gyazo.com/14c0d417ffb75a7c07f2587309541ae6

考えたこと

複数の山から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種か2種かそれ以上か、によってトップを取り除いた問題の「0が勝ちか負けか」に帰着される

ソートして線形に処理するだけなので間に合う

しかしこの考察をコンテスト中にリアルタイムでできる気がしないし、人間がやってるから見落とし経路とかありそう

リアルタイムでやるにはどうするのがいいのか。ソルバーを作って小さい問題を解いて、そこからパターン発見かなぁ

公式解説

だいぶシンプルな形に帰着されてた

コンテスト中にこの結論にたどり着くには、(メモ化) 再帰により小さいケースを解くプログラムを書 いたり、N = 2 のケースを紙と鉛筆で解くことで実験して仮説を立てる方法もあります。

まあそうなるのか〜

考えたこと3

そもそもこの問題、各山からの取るか取らないかの意思決定が他の山に全く干渉しないので、まずそれぞれの山が部分問題であると考えた方が良かったのではないか？

そもそも山一つの時に奇数が勝ちなのはこういう形だから

https://gyazo.com/cb838b2af7700f03a0a0700e26823b26

山二個の場合

https://gyazo.com/76f0d3348647f5f619903d283eb35839

負け状態を丸、丸に遷移可能な勝ち状態を四角、四角にしか遷移できない状態を丸にすると

https://gyazo.com/3389c6ac2c5426f784be4d9dfd140782

あー、なるほど、すべてが偶数である時に負け、という仮説が立てられる

1山ずつの部分問題の結合として考えた場合、すべてが0になれば負け

1手進めるか進めないかの選択肢がある

相手が1手進めた時にはこちらも同じことをすることによって偶奇を保つことができる