Google Code Jam 2019 Round 1C : C. Bacterial Tactics

まんまとミスした。
https://codingcompetitions.withgoogle.com/codejam/round/00000000000516b9/0000000000134cdf

問題

H*Wのグリッドがある。
一部のセルは放射能汚染されている。それ以外は初期状態では空マスである。

2人で交互にターンを迎えるゲームを行う。
各自の手番では以下を行う。

• 空マスを1個選択し、上下または左右のどちらかを選択して、グリッドの端または既に占領済みのマスに到達するまで占領する。
• ただし、占領範囲に汚染マスを含むことはできない(負けになる)
• 条件を満たす空マスが存在しない場合、その手番の人は負けとなる。

先手後手が最適手を打つ場合、先手が勝つ第1手目は何通りか。

解法

矩形領域のGrundy数を求めればNimに持ち込める。
矩形領域に対して1個マスを選択する処理を行うと2つ以下の矩形領域に持ち込めるので、その矩形領域のGrundy数のxorに対するmexを、元の矩形領域のGrundy数にすればよい。

サンプルはGrundy数でなく0/1(勝ち負け)だけ持っていても正答できてしまうので注意。

int H,W;
string S[15];

int gr[16][16][16][16];

int hoge(int y1,int y2,int x1,int x2) {
	if(y2<=y1||x2<=x1) return 0;
	if(gr[y1][y2][x1][x2]>=0) return gr[y1][y2][x1][x2];
	int x,y;
	set<int> T;
	for(y=y1;y<y2;y++) {
		int num=0;
		for(x=x1;x<x2;x++) num+=S[y][x]=='#';
		if(num==0) T.insert(hoge(y1,y,x1,x2)^hoge(y+1,y2,x1,x2));
	}
	for(x=x1;x<x2;x++) {
		int num=0;
		for(y=y1;y<y2;y++) num+=S[y][x]=='#';
		if(num==0) T.insert(hoge(y1,y2,x1,x)^hoge(y1,y2,x+1,x2));
	}
	gr[y1][y2][x1][x2]=0;
	while(T.count(gr[y1][y2][x1][x2])) gr[y1][y2][x1][x2]++;
	return gr[y1][y2][x1][x2];
	
}

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	
	cin>>H>>W;
	FOR(y,H) cin>>S[y];
	
	MINUS(gr);
	int ok=0;
	FOR(y,H) {
		if(count(ALL(S[y]),'#')==0 && (hoge(0,y,0,W)^hoge(y+1,H,0,W))==0) ok+=W;
	}
	FOR(x,W) {
		int num=0;
		FOR(y,H) num+=S[y][x]=='#';
		if(num==0 && (hoge(0,H,0,x)^hoge(0,H,x+1,W))==0) ok+=H;
	}
	
	_P("Case #%d: %d\n",_loop,ok);
}

まとめ

勝ち負けを持つのとGrundy数を持つの、たまに迷う。