CODE THANKS FESTIVAL 2014 B : G - 石取りゲーム

やっぱりA日程より簡単。正解者も多いしね。
http://code-thanks-festival-2014-b-open.contest.atcoder.jp/tasks/code_thanks_festival_14_qualb_g

問題

N個の石を使って２人でゲームを行う。
２人は交互に石を取っていく。

初手は先手は1～P個の範囲の石を取る。
以降、1～(直前の相手の取った石の数+1)の範囲の石を取る。
最後の石を取ったプレイヤーが勝利する。

N,Pが与えられたとき、両者が最適手を取ったときの勝者を答えよ。

解法

状態として(残りの石の数,取れる石の最大値)としてDFSで探索するだけ。
状態数がO(N^2)で、各状態の探索範囲がO(N)なので全体の計算量はO(N^3)だけど、実際遷移する状態はそこまで多くないので余裕で間に合う。

int memo[501][501];

int win(int N,int P) {
	int i;
	if(N<=P) return 1;
	if(memo[N][P]==-1) {
		memo[N][P]=0;
		for(i=1;i<=P;i++) {
			if(win(N-i,i+1)==0) memo[N][P]=1;
		}
	}
	return memo[N][P];
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	int N,P;
	
	MINUS(memo);
	cin>>N>>P;
	if(win(N,P)) _P("first\n");
	else _P("second\n");
}

まとめ

本番ここまで30分。あとはずっとH問題で悩んでた…。