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

問題文

解説

おそらく公式とは違う解法なのだと思う。
まず大きく二つのステップに分ける
①素数を全列挙する
②どっちが勝つかを考える

①素数を全列挙する

これは別にしなくてもいいのだが、計算量を減らすためにはやっておいた方がいい。
一般にある整数$N$が素数かどうかを判定するときは$2$~$\sqrt{N}$までで割り切れるかを確かめればいい。
これを繰り返し$2$~$N$までの素数チェックを行えれば大丈夫

②どっちが勝つかを考える

ここが難しいのだが、実はこのようなゲームでは次のような必勝法があるといわれている。
・自分がうまくやって負けの状態に遷移することができればその条件下では勝てる。
・そうでないならば勝てない。
まあこの感覚さえ覚えていればいい。
で、どうやるかというと、dpみたいな感じでやる
dp[$i$]=初めに自然数iが与えられたときに、先手が勝つことができるか。
ここが一番気持ち悪いだろうが、dp[$0$]とdp[$1$]はtrueにする。(当然勝てないので)。
つぎにdp[$i-素数$]がfalseになっているところがあるかについての判定は、①の配列を使えばいい。
これを繰り返していき、最後にdp[$N$]がtrueならWin,falseならLoseと置く。
（ここで、dp[$0$]およびdp[$1$]をtrueにした理由は、dp[$i$]がtrueならWinという感覚に合わせるとき、dp[$0$]dp[$1$]がfalseだとdp[$2$]がtrueになるといったかんじで勝敗が真逆になる現象が発生するためである）。
素数全列挙は$O(\sum_{i=1}^Nsqrt(i))$、dpは$O(N*素数の個数)$。
一つ目に関しては、$N=10000$と置いたとき$651750$。
$10000$以下の素数の個数は$1229$個なので、十分高速。

C++での解答例

#include <bits/stdc++.h>
using namespace std;

int main(){
  int n;cin>>n;
  //素数列挙
  vector<int> sosu(0);
  for(int i=2;i<=n;i++){
    bool sos=true;
    for(int j:sosu){
      if(i<j*j)break;
      if(i%j==0)sos=false;
    }
    if(sos)sosu.push_back(i);
  }
  vector<bool> dp(n+1,true);
  for(int i=2;i<=n;i++){
    bool win=false;
    for(int j:sosu){
      if(i<j)continue;
      if(!dp[i-j])win=true;
    }
    dp[i]=win;
  }
  cout<<(dp[n] ? "Win":"Lose")<<endl;
}