kmjp's blog

競技プログラミング参加記です

TopCoder SRM 778 : Div1 Hard DominoPlacement

いやこれ誤読なければ解けてるな。
https://community.topcoder.com/stat?c=problem_statement&pm=15896&rd=17805

問題

面積300以下のグリッドが与えられる。
一部のマスはすでに埋まっている。
空いているマスを1*KまたはK*1の形状の矩形で埋めるとき、その埋め方は何通りか。

解法

縦か横のどちらかは17以下になるので、必要なら回転して横幅を17以下とする。
上の行からBitDPで埋めていこう。

f(r,mask) := r行目において、(r+1)行目から上向きに連結したい列をbitmaskで指定されたとき、その通り連結できる組み合わせ
とする。
g(r,mask) := r行目において、(r+1)行目から上向きに連結可能な列がちょうどbitmaskの通りである組み合わせ
とする。
g(0,0)=1から初めて、g(r,*)からf(r,*)を求め、g(r+1,*)を求める、ということを順次行っていこう。
前者はg(r,*)を高速ゼータ変換で足しこむことでf(r,*)を求められる。
あとはf(r,*)からg(r+1,*)を求めるパートである。

まず、(r+1)列目で左に連結するマスをbitmaskで総当たりしよう。
左がすでに埋まったマスだったり、グリッド外である場合、そのbitmaskは無効である。
そうすると左右方向に連結する列が定まるので、残りのマスは上に連結してもいいししなくてもよい。
よってそのような上方向に連結可否が選べるbitmaskをbmとすると、bmの部分集合をsubmaskとすればf(r,submask)の合計が元の横方向連結を定めたときに組み合わせとなる。

なので、1行あたり高速ゼータ変換パートでO(2^W logW)、bitmask総当たりと部分集合を選ぶパートでO(3^W)で行ける。

ll from[1<<17];
ll to[1<<17];
const ll mo=1000000007;

int A[303];

class DominoPlacement {
	public:
	int countWays(vector <string> T) {
		int H=T.size();
		int W=T[0].size();
		ZERO(A);
		
		int y,x,mask;
		if(W>H) {
			FOR(y,H) FOR(x,W) if(T[y][x]=='#') A[x] |= 1<<y;
			swap(H,W);
		}
		else {
			FOR(y,H) FOR(x,W) if(T[y][x]=='#') A[y] |= 1<<x;
		}
		
		ZERO(from);
		from[0]=1;
		FOR(y,H) {
			
			ZERO(to);
			FOR(mask,1<<W) {
				if(mask&1) continue;
				int cmask=mask|(mask>>1);
				if(A[y]&cmask) continue;
				//cout<<y<<" "<<mask<<endl;
				int cand=((1<<W)-1)^(A[y]|cmask);
				for(int sub=cand;sub>=0;sub--) {
					sub&=cand;
					(to[cand]+=from[sub])%=mo;
				}
				to[cand]%=mo;
			}
			

			swap(from,to);
			FOR(x,W) FOR(mask,1<<W) if((mask&(1<<x))==0) (from[mask]+=from[mask^(1<<x)])%=mo;
		}
		
		return from[0];
	}
}

まとめ

本番1辺300と勘違いした…。