面倒だけどやり方はオーソドックスな問題。
http://community.topcoder.com/stat?c=problem_statement&pm=11506
問題
2人でゲームを行う。
状態の初期値を自然数Nとする。
先手後手ともに、交互にターンを行う。
各ターンでは、現在の状態から1~Kのいずれかの整数を減らすことができる。
ただし、減らした後の状態は:
- 先手は素数にしなければならない
- 後手は合成数にしなければならない
両プレイヤー、当然最適手を取る。
負けが確定しているプレイヤーはターン数を長引かせようとし、勝ちが確定しているプレイヤーはターン数を短くしようとする。
勝者および終了ターン数を答えよ。
解法
解法は割とオーソドックスで、「相手が負け確定の状態があるなら、そのうちターン数最小のものを選ぶ」「相手が負け確定の状態がないなら、こちらの負けが確定なのでターン数最大のものを選ぶ」をターン数を小さい順に定めていくだけ。
int NP,prime[100000]; const int prime_max = 474750; int p[prime_max]; void cprime() { int i,j; NP=0; for(i=2;i<prime_max;i++) { if(p[i]) continue; prime[NP++]=i; for(j=i*2;j<prime_max;j+=i) p[j]=i; } } bool win[500000]; int turn[500000]; class PrimeCompositeGame { public: int theOutcome(int N, int K) { int i,j,k,x,y; ZERO(p); cprime(); for(i=1;i<N;i++) p[i]=(p[i]==0); p[N]=0; ZERO(turn); ZERO(win); set<pair<int,int> > fw,fl,sw,sl; set<pair<int,int> >::iterator it; for(i=2;i<=N;i++) { j=i-K-1; if(j>1) { if(p[j]) { if(win[j]) sw.erase(make_pair(turn[j],j)); else sl.erase(make_pair(turn[j],j)); } else { if(win[j]) fw.erase(make_pair(turn[j],j)); else fl.erase(make_pair(turn[j],j)); } } if(p[i]) { if(!fl.empty()) { win[i]=1; it=fl.begin(); turn[i]=it->first+1; sw.insert(make_pair(turn[i],i)); } else { if(!fw.empty()) { it=fw.end(); it--; turn[i]=it->first+1; } sl.insert(make_pair(turn[i],i)); } } else { if(!sl.empty()) { win[i]=1; it=sl.begin(); turn[i]=it->first+1; fw.insert(make_pair(turn[i],i)); } else { if(!sw.empty()) { it=sw.end(); it--; turn[i]=it->first+1; } fl.insert(make_pair(turn[i],i)); } } } if(win[N]) return turn[N]; return -turn[N]; } };
まとめ
最初Grundy数かなと思ったけど違った。