Codeforces #179 Div1 D. Greg and Caves

自力で解けたし、意外と簡単だった問題。
http://codeforces.com/contest/295/problem/D

問題

グリッドのサイズNxMが与えられる。
初期状態ですべてのセルは白である。
ここで、以下のようにセルを黒く塗る方法は何通りあるか。

• [l,r]の範囲の行に、各行2セルずつ黒セルがある。それ以外に黒セルはない。
• [l,r]中のある行をtとすると：
  • [l,t]の範囲の行では、i行目の２つのセルで囲まれた列は、i+1行目の２つのセルで囲まれた列のサブセットである。
  • [t,r]の範囲の行では、i行目の２つのセルで囲まれた列は、i-1行目の２つのセルで囲まれた列のサブセットである。

解法

各行２つずつ黒セルがあると考えると面倒なので、まずその黒セルの間の列も塗りつぶして考える。
黒セルの形状は、下記の通りt行目が横幅が最大で、そこから上に行くほど幅が狭くなり、下に行っても幅が狭くなる。

...........
...........
.....##.... <- l 
....####...
....####...
....#####..
...######.. <- t
....###....
.....##.... <-r
...........

あとはガリガリ累積和を何度も取りつつDPしていく。
下記の手法では、t行目の幅と、tの値を総当たりし、t行目の上と下の行の形の組み合わせを列挙した。
t行目は幅が最大となる最初の行でなければならず、t行目より上は幅がt行目より細くなければならない(dp3)が、t行目より下は同じ幅でも良い(dp4)とした。

とにかく何度も累積和を取ることで、全体の計算量をO(NM)に抑える。
以下のコードは下記のように処理した。

• dp[x][y] : 幅がxで高さがyとなる構成の数。次の行は同じ幅でも良い。
• dp2[x][y] : 幅がxで高さがyとなる構成の数。次の行はxより細くなければならない。
• dp3[x][y] : dp2[x][0]～dp2[x][y]の累積和
• dp4[x][y] : dp3[x][0]～dp3[x][y]の累積和

int N,M;
ll mo=1000000007;

ll dp[2002][2002],dp2[2002][2002],dp3[2002][2002],dp4[2002][2002];

void solve() {
	int i,j,k,l,r,x,y,w; string s;
	
	cin>>N>>M;
	
	for(x=2;x<=2000;x++) dp[x][0]=dp2[x][0]=dp3[x][0]=dp4[x][0]=1;
	for(y=1;y<=2000;y++) {
		ll tot=0;
		for(x=2;x<=2000;x++) {
			tot+=dp[x][y-1];
			dp[x][y]=(dp[x-1][y]+tot)%mo; // same row
			dp2[x][y]=(dp[x][y]+mo-dp[x][y-1])%mo; // first shrink
			dp3[x][y]=(dp3[x][y-1]+dp2[x][y])%mo; // sum1
			dp4[x][y]=(dp4[x][y-1]+dp3[x][y])%mo; // sum2
		}
	}
	
	ll ret=0;
	for(w=2;w<=M;w++) {
		ll tmp=0;
		FOR(y,N) tmp+=dp3[w][y]*dp4[w][N-1-y]%mo;
		ret+=tmp*(M+1-w)%mo;
	}
	cout << ret%mo << endl;
}

まとめ

こんなに累積和取りまくったの久しぶり。