Codeforces #173 Div2. D. Yet Another Number Game

さてD。だんだん難しくなってきた。
http://codeforces.com/contest/282/problem/D

問題

最大３個のN=300以下の数値が与えられる。
ここで２人で交代にターンが回るゲームを行う。
自分のターンでは以下のいずれかを行う。いずれも行えなければ負け。

• 1つ数値を選び、そこから1～(その値)のいずれかを引く
• 1～(各数値の最小値)のいずれかを全部の数値から引く

両者が最適な行動をとる場合の勝者を答える。

解法

数値の数ごとに解法が異なる。

数値が1個の場合

• 数値が0なら先手が負け
• 数値が1以上なら、先手がそれをすべて引いてしまえば先手の勝ち

数値が2個の場合

メモ化再帰で処理する。
各自自分のターンの全選択肢をためし、相手が勝てない手段を取ればよい。
状態数は２つの値それぞれの組み合わせでO(N^2)、１回の処理でO(N)のループを回すので、全体でO(N^3)程度だが時間は問題ない。

数値が3個の場合

メモ化再帰だとO(N^4)になるので間に合わない。
ここで、各ターンで行う２個の処理のうち前者はNimそのものである。
よってまず後者の全選択肢を試して、相手が必敗のパターンがあれば勝ち。
そうでない場合、３つの数値のxorが0以外なら勝ち。

int N;
int A[5];
int memo[301][301];
int memo2[301][301][301];

int win2(int A,int B) {
	if(memo[A][B]>=0) return memo[A][B];
	if(A==0 && B==0) return memo[A][B]=0;
	if(A==0 || B==0) return memo[A][B]=1;
	
	int i;
	for(i=min(A,B);i>0;i--) if(win2(A-i,B-i)==0) return memo[A][B]=1;
	for(i=A;i>0;i--) if(win2(A-i,B)==0) return memo[A][B]=1;
	for(i=B;i>0;i--) if(win2(A,B-i)==0) return memo[A][B]=1;
	return memo[A][B]=0;
}

int win3(int A,int B,int C) {
	int i;
	
	if(memo2[A][B][C]>=0) return memo2[A][B][C];
	
	for(i=C;i>0;i--) if(win3(A-i,B-i,C-i)==0) return memo2[A][B][C]=1;
	return memo2[A][B][C]=((A^B^C)!=0);
}

void solve() {
	int i,j,k,x,y;
	
	N=GETi();
	FOR(i,N) A[i]=GETi();
	sort(A,A+N);
	reverse(A,A+N);
	MINUS(memo);
	MINUS(memo2);
	
	if(N==1) _P(A[0]?"BitLGM\n":"BitAryo\n");
	else if(N==2) _P(win2(A[0],A[1])?"BitLGM\n":"BitAryo\n");
	else _P(win3(A[0],A[1],A[2])?"BitLGM\n":"BitAryo\n");
	
	return;
}

まとめ

数値が3個の場合、Nimに落とし込むってのがとっさに思い浮かばなかった。
そりゃ考えてみりゃNimだな。