Typical DP Contest : S - マス目

最近TDPCのWriter一言解法紹介を見て、「あれ、今ならこれ解けるんじゃない？」と思ってチャレンジ。
http://tdpc.contest.atcoder.jp/tasks/tdpc_grid

問題

H*Wマスのグリッドを考える。
各マスは白黒を塗り分けたとき、左上角のマスから隣接する黒マスを辿って右下角のマスに辿りつけるような塗り分け方は何通りあるか。

解法

Hの上限が6と非常に小さい。

ここはめぐるはめぐる(4)の知見を活かして解こう。
yukicoder : No.234 めぐるはめぐる (4) - kmjp's blog

左から順に列ごとにbitDPの要領で解く。
最大で高さが6のため、その6個を白黒で塗ると、連結した黒マス領域群は最大3個となる。
よって各マス2bitで以下のように状態を(4^H)bitにエンコードする。

0:白マス
1:黒のうち左上と連結するマス
2,3:黒のうち、それぞれ左上とは連結しないマス(同じ数字は連結しているとみなす)

これに対し、次の列の白黒の組み合わせは(2^H)通りある。
この時次の列の状態がどうなるかを再び2bitにエンコードしていく。
自分はこの際Union-Findを使い連結マスを管理した。

2つの列の状態に対する状態遷移が計算できれば、後は1列ずつ組み合わせ数を足しこんでいくだけ。
計算量はO(2^(3*H)*W)位か。

template<int um> class UF {
	public:
	vector<int> par,rank;
	UF() {rank=vector<int>(um,0); for(int i=0;i<um;i++) par.push_back(i);}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};

ll mo=1000000007;
ll dp[105][1<<12];
int table[1<<12][1<<6];
int H,W;

int calctable(int m1,int m2) {
	int x,y,i;
	int mi[12]={};
	UF<12> uf;
	FOR(y,6) {
		i=(m1>>(y*2))&3;
		if(i==0) mi[y]=20;
		else mi[y]=i-1;
		
		if(m2&(1<<y)) mi[y+6]=10+y;
		else mi[y+6]=20;
	}
	FOR(y,6) {
		if(y && mi[y]<20 && mi[y-1]<20) uf(y,y-1);
		if(y && mi[y+6]<20 && mi[y-1+6]<20) uf(y+6,y-1+6);
		if(mi[y]<20 && mi[y+6]<20) uf(y,6+y);
	}
	FOR(y,6) FOR(x,y) if(mi[x]==mi[y]) uf(x,y);
	
	vector<int> v;
	FOR(y,12) mi[uf[y]]=min(mi[uf[y]],mi[y]);
	FOR(y,6) if(mi[uf[y+6]]<20) v.push_back(mi[uf[y+6]]);
	sort(ALL(v));
	v.erase(unique(ALL(v)),v.end());
	if(v.empty() || v[0]!=0) return -1;
	
	int ret=0;
	FOR(y,6) {
		if(mi[uf[y+6]]==20) x=0;
		else x=lower_bound(ALL(v),mi[uf[y+6]])-v.begin()+1;
		ret |= x<<(2*y);
	}
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	
	dp[0][1]=1;
	cin>>H>>W;
	FOR(i,1<<(2*H)) FOR(j,1<<H) table[i][j]=calctable(i,j);
	
	FOR(x,W) {
		FOR(i,1<<(2*H)) if(dp[x][i]) {
			FOR(j,1<<H) if(table[i][j]>=0) {
				dp[x+1][table[i][j]] += dp[x][i];
				if(dp[x+1][table[i][j]]>=mo) dp[x+1][table[i][j]]-=mo;
			}
		}
	}
	ll ret=0;
	FOR(i,1<<(2*H)) if(((i>>(2*(H-1)))&3)==1) ret += dp[W][i];
	cout<<ret%mo<<endl;
}

まとめ

ややこしい問題だけど、めぐるはめぐる(4)よりはだいぶマシ。