TopCoder SRM 523 Div2 Hard SmallBricks31

これはすんなり解けた。
http://community.topcoder.com/stat?c=problem_statement&pm=11549

問題

奥行１マス、幅Wマスのレゴ風ブロックがある。
ここに幅1,2,3マスのブロックを重ねていく。
ただ、不安定な置き方をしたくないので、３マスブロックの真ん中を除き、下にブロックが置けないような置き方をしたくない。

幅W,高さHの範囲で不安定でないブロックの重ね方は何通りあるか答えよ。

解法

Wが高々10なので、１つ下の段と現在の段を2^10通りDPしてしまえばよい。

下にブロックがない場所の上にブロックを積みたい場合、下の両隣にブロックがあってその上に３マスブロックが乗る場合しか許されない。
それ以外の場所は1,2,3マスブロックを任意に配置できるので、事前に１列分のブロックパターン2^W通りを実現する組み合わせ数を列挙しておくとよい。

ll mo=1000000007;
ll dpr[11];
class SmallBricks31 {
	public:
	int w;
	
	ll dp[12][1024];
	ll getr(int mask) {
		int x,bw;
		ll ret=1;
		if(dpr[1]==0) {
			dpr[0]=1;
			dpr[1]=1;
			dpr[2]=2;
			for(x=3;x<=10;x++) dpr[x]=dpr[x-1]+dpr[x-2]+dpr[x-3];
		}
		bw=0;
		FOR(x,w) {
			if(mask&(1<<x)) bw++;
			else ret*=dpr[bw],bw=0;
		}
		return (ret*dpr[bw])%mo;
	}
	
	int countWays(int w, int h) {
		int x,y,mask,nmask;
		this->w=w;
		
		ZERO(dp);
		dp[0][(1<<w)-1]=1;
		FOR(y,h) FOR(mask,1<<w) {
			FOR(nmask,1<<w) {
				int mu=0;
				int ng=0;
				FOR(x,w) if(((mask&(1<<x))==0) && (nmask&(1<<x))) {
					if(x==0 || x==w-1) ng++;
					else {
						if ((mask&(1<<(x-1)))==0 || (mask&(1<<(x+1)))==0) ng++;
						if ((nmask&(1<<(x-1)))==0 || (nmask&(1<<(x+1)))==0) ng++;
						if (mu&(1<<(x-1)) || mu&(1<<(x+1))) ng++;
						mu |= (1<<x) | (1<<(x-1)) | (1<<(x+1));
					}
				}
				if(ng) continue;
				dp[y+1][nmask] += getr(nmask^mu) * dp[y][mask];
				dp[y+1][nmask] %= mo;
			}
		}
		
		ll ret=0;
		FOR(mask,1<<w) ret+=dp[h][mask];
		return (int)(ret%mo);
	}
};

まとめ

N<=10ならbitDPを２段で行う(2^N)^2も間に合うんだな。