MemSQL start[c]up Round 2 : C. More Reclamation

自力で解けはしたけど妙に面倒な問題。
http://codeforces.com/contest/335/problem/C

問題

幅2、高さHのグリッドで、２人でゲームを行う。
両者は、相互に空きマスを取り合う。
両プレイヤーがあるマス(x,y)をとると、そのマスと(1-x,y-1)(1-x,y)(1-x,y+1)の３マスが使用不可となる。

初期状態としてHと初期状態で利用不可なマスが与えられる場合、両プレイヤーが最適行動をとる場合の勝者を答えよ。

解法

典型的なNim問題。
１つマスをとると、そのマスと横のマスが利用不可になり、残りの使用可能マスはそのマスの上側と下側に分断される。
よって空きマスの塊にGrundy数を割り当てればよい。
空きマスの状態は、左側と右側でそれぞれ上端と下端が１マスまでしかずれないので、状態数は9H程度に収まる。

H<=100なので、9H個の状態でそれぞれ最大2Hの空きマスを総当たりしてGrundy数を求めても計算は間に合う。

int H,N;
int NG[101][2];
int gr[103][3][3];

int grundy(int h,int ds,int db) {
	int i,j,k;
	if(h==-1 && ds==0 && db==2) return 1;
	if(h<0) return 0;
	if(gr[h][ds][db]!=-1) return gr[h][ds][db];
	
	int grm[100];
	ZERO(grm);
	//left
	FOR(i,h) grm[grundy(i,ds,0)^grundy(h-i-1,2,db)]=1;
	//right
	for(i=ds-1;i<h+db-1;i++) grm[grundy(i-1,ds,2)^grundy(h-i-2,0,db)]=1;
	
	gr[h][ds][db]=0;
	while(grm[gr[h][ds][db]]) gr[h][ds][db]++;
	return gr[h][ds][db];
}

void solve() {
	int f,i,j,k,l, x,y;
	
	cin>>H>>N;
	MINUS(gr);
	FOR(i,103) FOR(x,3) FOR(y,3) if(gr[i][x][y]==-1) grundy(i,x,y);
	
	FOR(i,N) {
		cin>>x>>y;
		x--;y--;
		NG[x][y]=NG[x][1-y]=1;
		if(x>0) NG[x-1][1-y]=1;
		if(x<H-1) NG[x+1][1-y]=1;
	}
	
	int nim=0,h,ds,db;
	for(x=0;x<H;) {
		if(NG[x][0] && NG[x][1]) {
			x++;
			continue;
		}
		
		h=0;
		if(NG[x][0]==0 && NG[x][1]==0) ds=1;
		else if(NG[x][0]==0 && NG[x][1]==1) h++,ds=2;
		else if(NG[x][0]==1 && NG[x][1]==0) x++,ds=0;
		while(x+h < H && (NG[x+h][0]==0 && NG[x+h][1]==0)) h++;
		
		if(x+h==H || (NG[x+h][0]==NG[x+h][1])) db=1;
		else if(NG[x+h][0]==0) h++,db=0;
		else x++,db=2;
		
		nim ^= gr[h][ds][db];
		x+=h;
	}
	if(nim==0) _P("LOSE\n");
	else _P("WIN\n");
}

まとめ

設定は面白いけど解くのは面倒だな…。