JOI Open Contest 2012 : A - Code

参加はしてないけど練習。
http://joiopen2012.contest.atcoder.jp/tasks/apio_code

アルファベットが長方形状に並んでいるとき、左上から右下まで最短経路で移動する場合に通るパスの文字列の種類の期待値を求める問題。
DPで解くんだろうなと思いつつ、うまくDPが組めなかったので他の回答を参考に解いた。

問題は、同じパターンの文字列の数をどうカウントしていくか。
左上から右下にかけてDPしていくんだけど、dステップ目では(0,d-1)～(d-1,0)のd個の文字に対し、互いに同じパターンが何個あるか累積値を持っておく。
状態としてはd^2だね。(自分自身とは同じパターンになるので、常に0よりは大きい)

d+1ステップを行う場合は、(0,d)～(d,0)の(d+1)^2個の組み合わせについて、文字が同じだったら先ほどの累積値を足しこんでいく。
d+1ステップ目のマス目は、dステップ目のマス目の左から入る場合と上から入る場合があるので注意する。
計算量はO(N^3)なので、N=300程度なら何とかいける。

int R,C;
char str[700][700];
int mo=1000000007;
s64 dp[2][400][400];

void solve() {
	int x,y,i,j,dist,t1,t2,tx,ty,dx,dy,m;
	s64 res=4;
	
	GET2(&R,&C);
	ZERO(str);
	FOR(y,R) GETs(str[y]);
	
	ZERO(dp);
	dp[0][0][0]=4;
	
	for(dist=1;dist<=R+C-1;dist++) {
		t1 = dist%2;
		t2 = 1-t1;
		
		FOR(tx,dist+1) {
			if(tx>=C) continue;
			ty = dist-tx;
			if(ty<0 || ty>=R) continue;
			
			FOR(dx,dist+1) {
				if(dx>=C) continue;
				dy = dist-dx;
				if(dy<0 || dy>=R) continue;
				
				dp[t1][tx][dx]=0;
				//_P("%d %d,%d %d,%d %d\n",dist,tx,ty,dx,dy,dp[t1][tx][dx]);
				
				if(str[ty][tx]!=str[dy][dx]) continue;
				//Tに上から入る
				if(ty>0) {
					m=(tx==C-1)?2:1;
					//Dに上から入る
					if(dy>0) dp[t1][tx][dx] += m*dp[t2][tx][dx];
					//Dに左から入る
					if(dx>0) dp[t1][tx][dx] += m*dp[t2][tx][dx-1];
				}
				//Tに左から入る
				if(tx>0) {
					m=(ty==R-1)?2:1;
					if(dy>0) dp[t1][tx][dx] += m*dp[t2][tx-1][dx];
					//Dに左から入る
					if(dx>0) dp[t1][tx][dx] += m*dp[t2][tx-1][dx-1];
				}
				dp[t1][tx][dx] %= mo;
				res =dp[t1][tx][dx];
				//_P("%d %d %d %d\n",dist,tx,dx,dp[t1][tx][dx]);
			}
			
		}
	}
	
	_P("%lld\n",res);
}

まとめ

最初なんでこのDPでうまく行くのかわかんなかった。
こういうDPを自分でさらさら書けるようにならないとな。