AtCoder ARC #207 (AtCoder Japan Open -予選-) : D - Devourers and Cake

意外と短い。
https://atcoder.jp/contests/arc207/tasks/arc207_d

問題

H*Wのグリッドがあり、各セル0/1のいずれかが書かれている。
これを用いて2人のターン制のゲームを行う。
各ターンでは、残セルが0個にならないように、先頭行・最終行・先頭列・最終列のいずれかを削除する。
最終的に残セルが1個になったとき、その値が1なら先手、0なら後手の勝ちとする。

最適手を打った時、勝者はどちらか。

解法

愚直にDPなりメモ化再帰すると、O(H^2*W^2)かかる。
しかし、相手と対称の手を繰り返すことで、概ね勝負はグリッドの中心部分で決まることがわかる。
そのため、中心の数列・数行付近でだけメモ化再帰すればよい。

int T,H,W;
string S[1010];
map<array<int,4>,int> memo;

int dfs(int L,int R,int U,int D,int t) {
	if(L==R&&U==D) {
		return S[U][L]==t+'0';
	}
	if(memo.count({L,R,U,D})) return memo[{L,R,U,D}];
	int win=0;
	if(L<R) {
		if(dfs(L+1,R,U,D,t^1)==0) win=1;
		if(dfs(L,R-1,U,D,t^1)==0) win=1;
	}
	if(U<D) {
		if(dfs(L,R,U+1,D,t^1)==0) win=1;
		if(dfs(L,R,U,D-1,t^1)==0) win=1;
	}
	return memo[{L,R,U,D}]=win;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>H>>W;
		FOR(y,H) cin>>S[y];
		int L=0,R=W-1;
		int U=0,D=H-1;
		while(R-L>=8) L++,R--;
		while(D-U>=8) U++,D--;
		memo.clear();
		
		if(dfs(L,R,U,D,1)) {
			cout<<"First"<<endl;
		}
		else {
			cout<<"Second"<<endl;
		}
		
	}
}

まとめ

解説にある場合分けよりも、範囲を絞ってメモ化再帰ゴリ押しの方が実装軽そう。