Codeforces #316 Div2 E. Pig and Palindromes

本番解ききれなかった、残念。
http://codeforces.com/contest/570/problem/E

問題

N*Mの２次元グリッドがある。
各セルにはアルファベットが１文字振られている。

このグリッド上で、左上角のセルから、右隣または下隣のセルを辿り、右下角のセルに到達したい。
その際、通ったセルのアルファベットを順に連結すると回文となるようにしたい。
そのような辿り方は何通りあるか。

解法

回文を作ろうと考えるのではなく、左上セルから右下に進むと同時に、右下から左上に進み、その際両者同じ文字のマスを経由するように進んで中央で遭遇させることを考えればよい。
dp[移動の回数][左上から移動してきた現在のセル][右下から移動してきた現在のセル]=条件を満たす辿り方の組み合わせ数
としてDPしていく。

このままだとメモリ容量も計算時間も(N≒Mとして)O(N^3)程度かかる。
今回のケースは時間はO(N^3)でも間に合うがメモリ容量が不足してしまう。
実際はi回目の移動時の値は(i-1)回目の移動時の値のみから計算できるので、『dp[移動の回数]」の部分は２回分だけメモリを確保すればよい。

int H,W;
string A[505];
ll mo=1000000007;
ll dp[2][505][505];

void solve() {
	int i,j,k,l,r,x,y; string s;
	int x1,x2,y1,y2;
	
	cin>>H>>W;
	FOR(y,H) cin>>A[y];
	
	dp[0][0][W-1]=A[0][0]==A[H-1][W-1];
	FOR(i,(H+W-2)/2) {
		int cur=i%2,tar=cur^1;
		ZERO(dp[tar]);
		FOR(x1,W) {
			y1=i-x1;
			if(y1<0 || y1>=H) continue;
			for(x2=x1;x2<W;x2++) {
				y2=H-1-(i-(W-1-x2));
				if(y2<0 || y2>=H || y1>y2) continue;
				if(dp[cur][x1][x2]==0) continue;
				FOR(j,4) {
					int nx1=x1,ny1=y1,nx2=x2,ny2=y2;
					if(j%2) nx1++;
					else ny1++;
					if(j/2) nx2--;
					else ny2--;
					if(nx1<=nx2 && ny1<=ny2 && A[ny1][nx1]==A[ny2][nx2]) (dp[tar][nx1][nx2]+=dp[cur][x1][x2])%=mo;
				}
			}
		}
	}
	
	ll ret=0;
	FOR(x1,W) FOR(x2,W) ret+=dp[(H+W-2)/2%2][x1][x2];
	cout<<ret%mo<<endl;
}

まとめ

N=500程度だとO(N^3)は計算時間は間に合うがメモリが不足する可能性がある、という点に注意しなくては。