Codeforces #167 Div1 D. Dima and Figure

こういうのはシンプルだけど割と好き。
http://codeforces.com/contest/273/problem/D

問題

NxMの2次元グリッドがある。
ここで以下の条件を満たすように幾つかのセルを黒く塗る。

• 最低1個以上のセルを塗る。
• 黒セル同士は隣接セルをたどり連結している。
• 黒セル(x1,y1)と(x2,y2)は黒セルだけを通り移動距離|x1-x2|+|y1-y2|で到達できる。

このような塗り分けは何通りできるか。

解法

上記条件を言い換えると、最終的な黒セル群について、各行の左端のセルが左に凸になっており、右端のセルが右に凸になっていればよい。
左端が凸ということは、上の行から見ると最初は左方向に左端が動き、頂点を超えると右方向に左端が動く。
右端も同様。

よって、dp[行番号][左端の位置][右端の位置][左端が頂点を超えたか？][右端が頂点を超えたか？]を状態にとってDPを行えばよい。
ただ、このままだと各行について、1行上の(左端・右端)から今の行の(左端・右端)にDPを行っていくので、(下記のコメント部のように)O(N*M^4)もかかりTLEする。
一部累積和を使うことでO(N*M^2)に押さえることができる。

ll dp[2][160][160][2][2];
ll S[160][160][2][2];
ll mo=1000000007;
int N,M;

ll diff(int x1,int x2,int y1,int y2,int ii,int jj) {
	ll ret=S[x2+1][y2+1][ii][jj]-S[x1][y2+1][ii][jj]-S[x2+1][y1][ii][jj]+S[x1][y1][ii][jj];
	return ((ret%mo)+mo)%mo;
}

void solve() {
	int i,j,k,l,r,x,y,x2,y2,h;
	
	cin>>N>>M;
	FOR(x,M) for(y=x;y<M;y++) dp[1][x][y][0][0]=1;
	
	ll ret=0;
	for(h=1;h<=N;h++) {
		ll tmp=0;
		int cur=h%2,tar=cur^1;
		FOR(x,M) for(y=x;y<M;y++) tmp+=dp[cur][x][y][0][0]+dp[cur][x][y][0][1]+dp[cur][x][y][1][0]+dp[cur][x][y][1][1];
		ret+=tmp%mo*(N+1-h);
		
		ZERO(S);
		ZERO(dp[tar]);
		FOR(i,2) FOR(j,2) {
			FOR(x,M) {
				FOR(y,M) S[x+1][y+1][i][j]=(S[x+1][y][i][j]+dp[cur][x][y][i][j])%mo;
				FOR(y,M) S[x+1][y+1][i][j]=(S[x+1][y+1][i][j]+S[x][y+1][i][j])%mo;
			}
		}
		
		FOR(x,M) for(y=x;y<M;y++) {
			ll(&to)[2][2]=dp[tar][x][y];
			to[0][0]+=diff(x,y,x,y,0,0);
			to[0][1]+=diff(x,y,y+1,M-1,0,0);
			to[1][0]+=diff(0,x-1,x,y,0,0);
			to[1][1]+=diff(0,x-1,y+1,M-1,0,0);
			
			to[0][1]+=diff(x,y,y,M-1,0,1);
			to[1][1]+=diff(0,x-1,y,M-1,0,1);
			
			to[1][0]+=diff(0,x,x,y,1,0);
			to[1][1]+=diff(0,x,y+1,M-1,1,0);
			
			to[1][1]+=diff(0,x,y,M-1,1,1);
			/* O(N*M^4)解
			FOR(x2,M) for(y2=x2;y2<M;y2++) {
				ll(&from)[2][2]=dp[cur][x2][y2];
				if(x2<x &&y2<y && x<=y2) to[1][0]+=from[0][0]+from[1][0];
				if(x2<x &&y2==y) to[1][0]+=from[0][0]+from[1][0], to[1][1]+=from[0][1]+from[1][1];
				if(x2<x &&y2>y ) to[1][1]+=from[0][0]+from[1][0]+from[0][1]+from[1][1];
				if(x2==x&&y2<y ) to[0][0]+=from[0][0], to[1][0]+=from[1][0];
				if(x2==x&&y2==y) to[0][0]+=from[0][0],to[0][1]+=from[0][1],to[1][0]+=from[1][0],to[1][1]+=from[1][1];
				if(x2==x&&y2>y ) to[0][1]+=from[0][0]+from[0][1],to[1][1]+=from[1][0]+from[1][1];
				if(x2>x &&y2<y ) to[0][0]+=from[0][0];
				if(x2>x &&y2==y) to[0][0]+=from[0][0],to[0][1]+=from[0][1];
				if(x2>x &&y2>y && y>=x2) to[0][1]+=from[0][0]+from[0][1];
			}
			*/
			to[0][0]%=mo;
			to[0][1]%=mo;
			to[1][0]%=mo;
			to[1][1]%=mo;
		}
	}
	cout << ret%mo << endl;
}

まとめ

累積和の取り方にだいぶ苦戦したけど、最終的には割と綺麗に書けたんじゃないかな。