読者です 読者をやめる 読者になる 読者になる

競プロ記録

問題を解いた際に自分の復習用として使ってます

No.8 N言っちゃダメゲーム

No.8 N言っちゃダメゲーム 解説

 

この問題はNとKが与えられ、Kを宣言したら負けとなるゲームです。

自分は必ず先攻で、相手は後攻です。

1〜Kの値までで加算して宣言することができます。

 

解答

この問題は自分がN−1をいうことができれば勝てます。

相手にN−1−K≦X≦N−2を相手に言わせれば良い。

自分はNー1ーKー1「Nー1ー(K+1)」を言えば勝てます。

 

相手にNー1ーKー1ーK≦X≦N−1ーKー1ー1を言わせれば良い

自分はNー1ーKー1ーKー1「Nー1ー2(K+1)」を言えば勝てます。

 

このように続けていくと「Nー1ーM(K+1)」(Mは定数)を言える時自分は勝つことがでいます。逆にこの値を相手に言わせてしまうと負けになります。自分は先攻で自分の初期状態は0であるためこの値が0と等しいと自分はこの値を宣言することができません。そのような場合相手は必勝法を使うため自分は勝てません。

つまり

Nー1ーM(K+1)=0

が成り立つ時

すなわち

N=M(K+1)+1の時

負けます。

したがって

N mod (K+1) == 1の時負けとなります。

 

以上解説でした。