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

問題

方針

\( K \geq N – 1 \) のときは先手必勝です。最終的に \( N – 1 \) を言うことができれば勝ちです。ここで、後手が言うことができる数字を考えます。先手がどのような数字を言ったとしても、\( n \) を自然数として、\( n(K + 1) \) を後手は必ず言うことができます。つまり、先手が加算した値を \( a + 1\) とすると、後手は \( K – a \) を加算した値を言うことで達成できます。したがって、\( (N – 1) \bmod (K + 1)  = 0 \) であれば後手が必勝です。

一方で、\( (N – 1) \bmod (K + 1)  \neq 0 \) のとき、先手は、\( (n – 1)(K + 1) + (N – 1) \bmod (K + 1) \) と言うことができます。また、\( (n – 1)(K + 1) + (N – 1) \bmod (K + 1) = N – 1\) となる \( n \) が存在するので、先手が必勝です。

コード

感想

こういう問題苦手です。