TopCoder SRM 526 Div1 Medium PrimeCompositeGame

面倒だけどやり方はオーソドックスな問題。
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数かなと思ったけど違った。