Codeforces #206 Div1. B. Game with Strings

問題を解くことよりも、題意を理解することの方が難しかった…。
http://codeforces.com/contest/354/problem/B

問題

NxNのグリッドの各マスにアルファベットが書かれている。
このグリッドを使って、２人で交互にターンをこなすゲームを行う。

• 両者の合計ターン数Tに対し、以下を満たすように左上マスから右方向または下方向にTマスたどるパスを取る。
  • その際、最初の(T-1)個のセルは、直前の(T-1)ターン目でたどった(T-1)セルと同じ文字列を成していなければならない(文字列が同じならパスが異なっていても良い)
• 最終的に、パスが右下に到達する(2N-1)ターンが終わったら終了。(2N-1)ターン後に生成される文字列において、"a"が"b"より多ければ先手勝ち、"b"が多ければ後手が勝ち。

両者が最適手を取ったときの勝者を求めよ。

解法

問題を読んだとき、Tターン目は(T-1)ターンのパスを伸ばさないといけないと勘違い。
(T-1)マスで生成される文字列が等しいなら、パス自体は(T-1)ターン目と同じでなくてもよいのだ。
この問題文を理解するのに１時間以上かかった…。

問題文を理解してしまうとだいぶ楽。
"a"と"b"の数の差を状態としてDP[ターン数][移動可能なマスのbitmask]に持ち、BitDPすればよい。
[移動可能なマスのbitmask]には、そのターンに同じ文字列を構成して到達できる各Y座標をbitmaskとして持つ。
あとは、この変数を奇数ステップは"a"が増え、偶数ステップは"b"が増える方向にDPする。

int N;
string T[30];
int dpdp[50][1<<21];

int dodo(int step,int mask) {
	int y,x,ch,r=0;
	
	if(dpdp[step][mask]!=-10000) return dpdp[step][mask];
	if(step==2*N-2) {
		dpdp[step][mask]=0;
		if(ch=='a') dpdp[step][mask]++;
		if(ch=='b') dpdp[step][mask]--;
		return dpdp[step][mask];
	}
	
	
	if(step%2) r=-1000;
	else r=1000;
	
	for(ch='a';ch<='z';ch++) {
		int nm=0;
		FOR(y,N) {
			if((mask & (1<<y))==0) continue;
			x=step-y;
			if(x<0 || x>=N) continue;
			if(x<N-1 && T[y][x+1]==ch) nm |= 1<<y;
			if(y<N-1 && T[y+1][x]==ch) nm |= 1<<(y+1);
		}
		int tmp = 0;
		if(ch=='a') tmp++;
		if(ch=='b') tmp--;
		if(nm==0) continue;
		if(step%2) r=max(r,tmp+dodo(step+1,nm));
		else r=min(r,tmp+dodo(step+1,nm));
	}
	return dpdp[step][mask]=r;
}

void solve() {
	int f,i,j,k,l, x,y;
	
	cin>>N;
	FOR(i,N) cin>>T[i];
	FOR(x,2*N) FOR(y,1<<20) dpdp[x][y]=-10000;
	l=dodo(0,1);
	if(T[0][0]=='a') l++;
	if(T[0][0]=='b') l--;
	
	if(l>0) _P("FIRST\n");
	else if(l<0) _P("SECOND\n");
	else _P("DRAW\n");
}

まとめ

自分以外にも問題文を誤読していた人がいたようだ。
そのためかこの問題はCより回答者が少ない。