TopCoder SRM 722 Div1 Hard DominoTiling

自分もグダグダだし、運営もグダグダになってしまった問題。
https://community.topcoder.com/stat?c=problem_statement&pm=14700

問題

H*Wのグリッドがあり、一部のマスは埋められている。
空きマスを1*2の大きさのブロックで埋めるとき、埋め方は何通りか。

解法

O(H*4^W)、O(H*3^W)、O(H*W*2^W)と色々な解法がある。
元のH,Wの上限からすると後ろ２つが想定っぽいが…H,Wがコンテスト中に上限を下げられたため、３つとも間に合うようになってしまった。

以下真ん中の解法を紹介。
１列ずつ埋めていくことを考える。
ある行を埋めたとき、縦２マスのブロックを配置することで、次の行のブロックも一部要するケースを考える。

次の行の配置を考えるとき、上の行に縦ブロックを置いたことで埋められてるケースを総当たりしよう。
元々すでに埋まっているマスと合わせ、残されたブロック群のbitmaskがわかる。
事前に空きブロックに対して縦横ブロックの置き方を列挙しておこう。
それらを総当たりし、次の行に縦ブロックがどのように埋まるかbitmask毎の組み合わせを求めていく。

ll from[1<<14];
ll to[1<<14];
vector<int> cand[1<<14];


class DominoTiling {
	public:
	int H,W;
	void dfs(int cm,int nm,int d) {
		if(d==W) {
			cand[cm].push_back(nm);
			return;
		}
		// non
		dfs(cm,nm,d+1);
		// yoko
		if(d+2<=W) dfs(cm|(3<<d),nm,d+2);
		// tate
		dfs(cm|(1<<d),nm|(1<<d),d+1);
	}
	long long count(vector <string> S) {
		int x,y,i,mask;
		H=S.size();
		W=S[0].size();
		
		FOR(mask,1<<W) cand[mask].clear();
		dfs(0,0,0);
		
		ZERO(from);
		ZERO(to);
		
		from[0]=1;
		FOR(y,H) {
			int bmask=0;
			FOR(x,W) if(S[y][x]=='X') bmask|=1<<x;
			ZERO(to);
			FOR(mask,1<<W) if(from[mask]) {
				if(mask&bmask) continue;
				int left=((1<<W)-1) ^ (mask|bmask);
				FORR(c,cand[left]) to[c]+=from[mask];
			}
			
			swap(from,to);
		}
		
		
		
		return from[0];
		
	}
}

まとめ

O(H*W*2^W)解法をなぜ思い浮かばなかった…。