Codeforces ECR #083 : F. Attack on Red Kingdom

この回は本番で完答できた。
http://codeforces.com/contest/1312/problem/F

問題

変則的なNimを行う。
両者山から一度に取り除ける石の数はX,Y,Zのいずれかである。
ただし石の数がX,Y,Z未満でもX,Y,Zを選択することができる。
また、Y,Zに対しては各山直前と同じパターンを連続して利用することはできない。

先手が必勝となる初手は何通りか。

解法

f(n,p) := 直前pの手を使ったとき、残りn個を使い切る場合のgrundy数
を考える。実際試してみると、X,Y,Zの値により周期は異なるがある程度大きいnでは周期性が生じる。
そうするとf(n,p)が大きいnに対しても求まるので、grundy数のxorを取っていこう。

int T;
int N,X,Y,Z;
ll A[303030];

int pat[6][6][6][3][1050];
int rep[6][6][6];

int grundy[2][2][1050];

int hoge(int cur,int p) {
	if(cur<=0) return pat[X][Y][Z][p][cur]=0;
	
	if(pat[X][Y][Z][p][cur]>=0) return pat[X][Y][Z][p][cur];
	set<int> S;
	S.insert(hoge(cur-X,0));
	if(p!=1) S.insert(hoge(cur-Y,1));
	if(p!=2) S.insert(hoge(cur-Z,2));
	int ret=0;
	while(S.count(ret)) ret++;
	
	return pat[X][Y][Z][p][cur]=ret;
	
	
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	MINUS(pat);
	for(X=1;X<=5;X++) for(Y=1;Y<=5;Y++) for(Z=1;Z<=5;Z++) {
		
		for(i=1;i<=1000;i++) hoge(i,0), hoge(i,1), hoge(i,2);
		
		for(i=1;i<=20;i++) {
			int ng=0;
			for(x=100;x<=1000;x++) {
				FOR(j,3) if(pat[X][Y][Z][j][x]!=pat[X][Y][Z][j][x-i]) ng=1;
			}
			if(ng==0) break;
		}
		rep[X][Y][Z]=i;
	}
	
	cin>>T;
	while(T--) {
		cin>>N>>X>>Y>>Z;
		
		int nim=0;
		FOR(i,N) {
			cin>>A[i];
			if(A[i]>100) A[i]=(A[i]-100)%rep[X][Y][Z]+100;
			nim^=pat[X][Y][Z][0][A[i]];
		}
		
		int ret=0;
		FOR(i,N) {
			if((hoge(A[i],0)^hoge(A[i]-X,0))==nim) ret++;
			if((hoge(A[i],0)^hoge(A[i]-Y,1))==nim) ret++;
			if((hoge(A[i],0)^hoge(A[i]-Z,2))==nim) ret++;
		}
		
		cout<<ret<<endl;
		
		
	}
}

まとめ

周期性があると気付いてしまえばあとはすぐ。