落書きの魔女 (AOJ2314)

苦行だった・・・

問題:
H*Wのマス目がある.それぞれを#か.で塗る いくつかは既にどれで塗るか決まっている.残りのマスの塗り方のうちもっとも#が多いもののマス目全体の#の数を答えよ.正しいかの条件を満たして塗る必要がある".は連結(4-neighborsで)しない","#が(4-neighborsで)木になっている"
H,W<=11.

解答:
面倒なことで有名な,連結状況を持ったbitDPをするだけ.
横一列W個の塗り方はフィボナッチ数233になり,接続関係は高々6個しか連結成分が現れないことを考えるとベル数の0~6項目までの和279くらいで抑えられる.頑張って先に塗り方や接続関係を列挙しとくと,前処理でnxt[i][j][k]=連結状況i,bitがjの時に次の行にbit kをおくと連結状況はどうなるか を超頑張れば求められる.あとはDP.

超頑張れば,というのが厄介で,連結状況って持ちにくくて(例えばvector >とか) いや作るのは簡単なんだけど,実際nxt[i][j][k]を求めようとする時にunionfindとかでもとまった状態からどの連結状況になってるかを求めるのが面倒なんですよね.これをゴリゴリやったせいでコードが200行くらいになってしまった.

で、もっと頭いい方法があって,一マスずつ埋めます.よくあるやつですね.蟻本にも載ってるし,完全に頭悪いやつだ.この方法に関しては公式スライドにのってる.

コード

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vv;
typedef pair<int,int> P;
vi con[279];			//sum of 0~6th Bell number
map<vi,int> inv;		//inv of con
int mx_[279];
int bits[234];			//11th Fibonacci number
vector<P> bitcon[234];	//11010 -> {(0,2),(3,4)}
short int nxt[279][234][234];
int C;	//con
int B;	//bits
int H,W;
string s[11];
int dp[12][279][234];
vi tmp;
void dfs(int x,int mx){
	con[C]=tmp;
	mx_[C]=mx;
	inv[tmp]=C++;
//	printf("c=%d:  ",C-1);
//	for(int a:tmp) cout<<a<<" ";
//	puts("");
	if(x==6) return;
	rep(i,mx+1){
		tmp.pb(i);
		dfs(x+1,max(mx,i+1));
		tmp.pop_back();
	}
}
inline int cntbit(int x){
	if(x==0) return 0;
	return __builtin_popcount(x);
}
int par[12];
void init(int N){rep(i,N) par[i]=i;}
int find(int x){
	if(par[x]==x) return x;
	return par[x]=find(par[x]);
}
bool same(int x,int y){
	return find(x)==find(y);
}
void unite(int x,int y){
	x=find(x),y=find(y);
	if(x<y) swap(x,y);
	par[x]=y;
}
inline bool _b(int x,int y){
	return ((x>>y)&1)==1;
}
bool is(P x,P y){
	return x.fs<y.sc&&y.fs<x.sc;
}
int main(){
	dfs(0,0);
	cin>>H>>W;
	rep(i,H) cin>>s[i];
	if(W==1){
		if(H==1){
			if(s[0][0]=='.') puts("0");
			else puts("1");
			return 0;
		}
		rep1(i,H-1) s[0]+=s[i][0];
		swap(H,W);
	}
	rep(i,1<<W){
		bool ok=1;
		rep(j,W-1) if( !_b(i,j) && !_b(i,j+1) ) ok=0;
		if(ok||i==0){
			bits[B]=i;
//			printf("bits[%d]=%d\n",B,i);
			int p=-1;
			vector<P> vp;
			rep(j,W+1){
				if(_b(i,j)){
					if(p<0) p=j;
				}else{
					if(p>=0){
						vp.pb(P(p,j));
						p=-1;
					}
				}
			}
			bitcon[B++]=vp;
//			show(vp.size());
		}
	}
//	show(B);
	rep(i,C) rep(j,B) rep(k,B) nxt[i][j][k]=-1;
	rep(i,C){
		vi& vc=con[i];
		int sz=vc.size();
		rep(j,B){
			int& b=bits[j];
			vector<P>& bc=bitcon[j];
			if(bc.size()!=sz) continue;
			rep(k,B){
				int& nb=bits[k];
				vector<P>& nbc=bitcon[k];
				int nsz=nbc.size();
				if((b|nb)!=(1<<W)-1 && j>0) continue;
				bool ok=1;
				rep(d,W-1) if(_b(b,d)&&_b(b,d+1)&&_b(nb,d)&&_b(nb,d+1)) ok=0;
				if(j>0&&!ok) continue;
//				if(i==4&&j==6&&k==10) puts("---!!---");
//				if(i==4&&j==6&&k==10) show(sz);
//				if(i==4&&j==6&&k==10) show(nsz);
				init(sz+nsz);
				rep(d,sz) rep(e,sz){
					if(vc[d]==vc[e]){
						unite(d+nsz,e+nsz);
//						if(i==4&&j==6&&k==10) printf("%d-%d\n",d+nsz,e+nsz);
					}
				}
				bool used[6]={};
				rep(d,sz) rep(e,nsz){
					if(is(bc[d],nbc[e])){
						if(same(d+nsz,e)){
							ok=0;
							goto done;
						}
						unite(d+nsz,e);
//						if(i==4&&j==6&&k==10) printf("%d-%d\n",d+nsz,e);
						used[vc[d]]=1;
					}
				}
				done:
				if(ok){
//				printf("'nxt[%d][%d][%d]=ok\n",i,j,k);
					rep(d,mx_[i]) if(!used[d]) ok=0;
					if(!ok) continue;
					vi nvc;
					map<int,int> mp;
					int Z=0;
					rep(d,nsz) if(mp.count(find(d))==0) mp[find(d)]=Z++;
					rep(d,nsz) nvc.pb(mp[find(d)]);
					if(inv.count(nvc)==0){
						show(nsz);
						for(int a:nvc) cout<<a<<" ";
						assert(false);
					}
					nxt[i][j][k]=inv[nvc];
//					printf("nxt[%d][%d][%d]=%d\n",i,j,k,nxt[i][j][k]);
//					for(int a:nvc) cout<<a<<" ";
//					puts("");
				}
			}
		}
	}
	if(W==1) nxt[1][1][0]=0;
	rep(i,H+1) rep(j,C) rep(k,B) dp[i][j][k]=-1;
	dp[0][0][0]=0;
	rep(i,H){
		bool canuse[234]={};
		rep(k,B){
			bool ok=1;
			rep(x,W){
				if(s[i][x]=='#'&&!_b(bits[k],x) ) ok=0;
				if(s[i][x]=='.'&& _b(bits[k],x) ) ok=0;
			}
			canuse[k]=ok;
//			if(ok) printf("canuse[%d]=%d\n",k,ok);
		}
		rep(j,C) rep(k,B){
			if(dp[i][j][k]<0) continue;
//			printf("i,j,k=(%d,%d,%d)\n",i,j,k);
			if(i>0&&k==0&&W>1) continue;
			rep(l,B){
				if(!canuse[l]) continue;
				if(W>1&&l==0) continue;
//				printf("  i,j,k=(%d,%d,%d)\n",i,j,k);
//				show(l);
//				show(nxt[j][k][l]);
				if(nxt[j][k][l]>=0){
					chmax(dp[i+1][nxt[j][k][l]][l],dp[i][j][k]+cntbit(bits[l]));
//					printf("dp[%d][%d][%d],dp[%d][%d][%d]+%d\n",i+1,nxt[j][k][l],l,i,j,k,cntbit(bits[l]));
				}
			}
		}
	}
	int ans=-1;
	rep(j,C){
		bool ok=1;
		rep(k,con[j].size()) if(con[j][k]>0) ok=0;
		if(!ok) continue;
//		show(j);
		rep(k,B){
			chmax(ans,dp[H][j][k]);
//			printf("dp[%d][%d][%d]=%d\n",H,j,k,dp[H][j][k]);
		}
	}
	cout<<ans<<endl;
}

闇