TopCoder SRM 526 Div1 Medium PrimeCompositeGame

問題

二人がN個の石の山を使って次のようなゲームをする。

  • 二人は交互に手番をまわす。操作のできなくなったプレイヤーの負けである。
  • 手番のプレイヤーは1以上K個以下の石を取る
  • 石を取り終えた後、先手は山の石の数が素数でなくてはならず、後手は石の数が合成数でなくてはならない。

プレイヤーは勝てるなら最短手数で、どうやっても負けるならなるべく長い手数で負けるように手を選ぶ。
お互いが最善を尽くすとしたとき、どちらのプレイヤーが何ターンで勝つかを求めよ。

制約条件

N≦50万くらい

方針

N≦2だったら先手負け。
3以上のとき、素数素数のギャップの最大値よりもkが大きければ先手の勝ちである。
(何故なら先手は必ず素数を取ることができて、後手は最後に取れるのは4で、その後先手が3を取れるから)


そうでないとき、kは120以下である(最も離れた素数間の距離は120程度である)ので、
O(NK)のDPをすればよい。


前者のとき、先手は最も小さい素数が残るように山から石を取ればよく、
後手は1個だけ山から石を取ればよい。

ソースコード

const int MX=500000;
int k;
vi prime;
bool p[MX];
pi dp[MX][2];
pi solve(int n,int turn){
  if(dp[n][turn].first)return dp[n][turn];
  if(n==2)return mp(turn?1:-1,0);
  if(n==3){
    if(!turn)return mp(1,1);
    return mp(1,0);
  }
  pi &res=dp[n][turn];
  if(turn==0){
    int win=inf,lose=-1;
    for(int i=1;i<=min(n-2,k);i++)if(!p[n-i]){
      pi tmp=solve(n-i,1-turn);
      if(tmp.first>0)win=min(win,tmp.second);
      else lose=max(lose,tmp.second);
    }
    if(win!=inf)return res=mp(1,1+win);
    return res=mp(-1,1+lose);
  }
  else{
    int win=inf,lose=-1;
    for(int i=1;i<=min(n-2,k);i++)if(p[n-i]){
      pi tmp=solve(n-i,1-turn);
      if(tmp.first<0)win=min(win,tmp.second);
      else lose=max(lose,tmp.second);
    }
    if(win!=inf)return res=mp(-1,1+win);
    return res=mp(1,1+lose);
  }
}

class PrimeCompositeGame {
  public:
  int theOutcome(int N, int K) {
    memset(p,0,sizeof(p));
    prime.clear();
    for(int i=2;i*i<MX;i++)if(!p[i])for(int j=i*i;j<MX;j+=i)p[j]=1;
    for(int i=2;i<MX;i++)if(!p[i])prime.pb(i);
    
    k=K;
    memset(dp,0,sizeof(dp));
    
    int gap=0;
    rep(i,prime.size()-1){
      if(prime[i+1]>N)break;
      gap=max(gap,prime[i+1]-prime[i]);
    }
    if(gap>k){
      pi ans=solve(N,0);
      return ans.first>0?ans.second:-ans.second;
    }
    
    int turn=0;
    for(;N;turn++){
      if(turn%2){
        N--;
        if(N<4||!p[N])return turn;
      }
      else{
        if(*lower_bound(all(prime),N-K)>=N)return -turn;
        N=*lower_bound(all(prime),N-K);
      }
    }
    return 0;
  }
};