TopCoder SRM 637 Div1 Medium PathGame

色々細かいミスをして本番に解ききれず。
http://community.topcoder.com/stat?c=problem_statement&pm=13438

問題

縦H行横W列かのグリッドがある。ただしH=2固定である。
各セルは白マスか黒マスのいずれかであり、黒マスは移動できない。

初期状態では、左端の上下いずれかのセルから、右端の上下いずれかのセルに隣接する白マスをたどって移動可能なことが保証されている。

ここで２人でゲームを行う。
両者は順番でターンが回ってくる。
自分のターンでは、いずれかの白マスを１つ黒マスにしなければならない。
その際、左端から右端に移動不可能となる白マスは選択できない。
自分のターンで選択可能な白マスがない場合、負けとなる。

両者が最適手を取った場合、先手後手どちらが勝つか。

解法

実はほぼ同じ問題が既出である。
MemSQL start[c]up Round 2: C. More Reclamation - kmjp's blog

R行C列に黒マスがあると、(R^1)行(C-1)列、(R^1)行C列、(R^1)行(C+1)列に黒マスを置くと移動が不可能となる。
あとは移動可能な白マスを連結した形状に対しGrundy数を求めて、Nimのように解けばよい。

白マスの連結成分は、２つの行は左端と右端は±1しかずれないので、状態は[１行目の白マスの連続数][２行目の左端の１行目との相対位置][２行目の右端の１行目との相対位置]のように取れば空間計算量はO(W)で済み、全体の計算時間もO(W^2)ですむ。

なお、Write想定解は別解であるようだ。
SRM637 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ

int grundy[3][1001][3];

class PathGame {
	public:
	int H,W;
	int getgr(int d,int w,int w2) {
		set<int> me;
		int r=0,i;
		if(w==0 && d==0 && w2==1) return 1;
		if(w<=0) return 0;
		if(grundy[d][w][w2+1]>=0) return grundy[d][w][w2+1];
		
		FOR(i,w) me.insert(getgr(d,i,-1)^getgr(1,w-1-i,w2));
		for(i=d;i<w+w2;i++) me.insert(getgr(d,i-1,1)^getgr(1,w+w2-1-i,-w2));
		
		while(me.count(r)) r++;
		return grundy[d][w][w2+1]=r;
	}
	
	string judge(vector <string> board) {
		int x,y;
		W=board[0].size();
		FOR(y,2) FOR(x,W) if(board[y][x]=='#') {
			if(x>0 && board[y^1][x-1]) board[y^1][x-1]='*';
			if(board[y^1][x]) board[y^1][x]='*';
			if(x<W-1 && board[y^1][x+1]) board[y^1][x+1]='*';
		}
		
		MINUS(grundy);
		int gr=0,aa=0;
		FOR(x,W) FOR(y,2) if(board[y][x]=='.') {
			int cx=x,d=0,w=0,w2=0;
			while(cx+w<W && board[y][cx+w]=='.') board[y][cx+w]='a'+aa, w++;
			w2=d=(board[y^1][cx]!='.');
			while(cx+w2<W && board[y^1][cx+w2]=='.') board[y^1][cx+w2]='a'+aa, w2++;
			if(aa++>=26) aa=0;
			gr ^= getgr(d,w,w2-w);
		}
		cout << board[0] << endl;
		cout << board[1] << endl;
		return (gr==0)?"Sothe":"Snuke";
	}
}

まとめ

本番Codeforces系で既出だったことまで思い出せたけど、どのコンテストかまでは思い出せなかった。
そしてGrundy数を再実装して何か所もバグ。もったいないなぁ。