山傘のプログラミング勉強日記[Java & Unity]

プログラミングに関する日記とどうでもよい雑記からなるブログです。

[yukicoder] No.7 プライムナンバーゲーム [レベル: 2]

Groudy数

問題

No.7 プライムナンバーゲーム - yukicoder

解説記事を読むとこのような問題はGroudy数というようです。

Grundy数 - CCS Wiki

考え方

 N 以下の素数の配列  P を昇順にならべて用意します。

 i = 2 から i = N まで順番に先手が勝つか後手が勝つかを記録していきます。

この勝敗の配列を  S とし0勝ち、1を負けとします。この配列の初期値は1としておきます。例えば、 S[2] = 1 S[3] = 1 S[4] = 0 となっています。

次に、 a = N - P[i] を計算し、 1 \leq a \leq 3 となる aが存在すれば先手が勝ちとなります。つまり、 S[i] = 0 です。

上記以外の場合、 S[a] = 1 となる a が存在すれば先手が勝ちになります。これは、 i を調べる時点で、 i - 1 以下の数の勝敗が分かっているので、 S[a] = 1 ということは、先後が入れ替わり、後手が N = a からゲームをやるということです。つまり、後手が負けることを意味します。

上記以外の場合は、後手が勝ちます。

正直、解説があっているどうか自信がないですが、コードは正解となりました。レベル2ということもあり、難しかったです。