TopCoder SRM 671 Div2 Hard BearDestroysDiv2

なかなか面白い問題。Div2とDiv1の制限のかけ方が珍しい。
http://community.topcoder.com/stat?c=problem_statement&pm=14070

問題

W*Hの大きさのグリッド状の森がある。
各マスには木が１本たっており、各木は右か下どちらかに倒れやすい。
そのため、森全体での木の倒れやすさの組み合わせは2^(W*H)通りある。

木を右か下に倒すと、木のあったマスと倒れた先の隣接マスの計２マスは立ち入りできなくなる。
ここでクマが以下の条件で森中の木を倒して行く。

• クマは左上から右方向に移動し、右端に到達したら１つ下の行の左端に移動する、という順でマスを辿る。
• 今いるマスに(上や左から)倒れた木が来ていないなら、以下の優先順位でマスの木を倒すことを試みる。
  • 木の倒れやすい方に倒しても、倒した先が森からはみ出たり他の倒れた木とマスを共有しないなら、その方向に倒す。
  • 倒れやすい方に倒せないなら、右と下逆向きの方向に(同上の条件を満たすなら)倒す。
  • どちらにも倒せないなら倒さない。

2^(W*H)通りの森の状態それぞれについて、倒せる木の数の総和を求めよ。

解法

Wが小さいので、上の行からbitDPしていこう。
各行では(2^W)*(2^W)通りのbitDPを行う。
各マスについて、「各セルが上の行から木が倒れてきているかどうか否か」で2^W通り、「各セルが右としたどちらに倒れやすいか」で2^W通りである。

状態としては
dp[処理した行番号][倒れた木の総数][次の行に向け倒れた木のbitmask] := その状態になる組み合わせ数
を持ち、最後にi*dp[H][i][0]の総和を取ればよい。
O((W*H)^2*4^W)程度かかるが、Wが小さいので割と余裕で間に合う。

ll dp[51][150][1<<8];

class BearDestroysDiv2 {
	public:
	int sumUp(int W, int H, int MOD) {
		ll mo=MOD;
		int x,y,fmask,tmask,n;
		
		ll pat=1;
		FOR(x,W*H-1) pat=pat*2%mo;
		
		ZERO(dp);
		dp[0][0][0]=1;
		FOR(y,H) {
			FOR(n,145) FOR(fmask,1<<W) if(dp[y][n][fmask]) {
				FOR(tmask,1<<W) {
					int nm=0,fall=0;
					int fmask2=fmask;
					FOR(x,W) if((fmask2&(1<<x))==0) {
						if(tmask&(1<<x)) { // right
							if(x<W-1 && (fmask2&(1<<(x+1)))==0) fmask2 |= 1<<(x+1), fall++;
							else if(y<H-1) nm |= 1<<x, fall++;
						}
						else {
							if(y<H-1) nm |= 1<<x, fall++;
							else if(x<W-1 && (fmask2&(1<<(x+1)))==0) fmask2 |= 1<<(x+1), fall++;
						}
					}
					(dp[y+1][n+fall][nm] += dp[y][n][fmask])%=mo;
				}
			}
		}
		
		ll ret=0;
		FOR(n,145) ret += n*dp[H][n][0]%mo;
		
		return ret%mo;
		
	}
}

まとめ

あれ、Div2の方問題文が間違ってる？（入力にMODがない）