Codeforces #298 Div2 F. Simplified Nonogram

なんとか本番解けた。
http://codeforces.com/contest/534/problem/F

問題

R*Cの２次元グリッドの各セルを白黒で塗り分けたい。
１つの列または行で連続した黒セルを1セグメントとカウントするとき、各行rのセグメント数A[r]及び各列cのセグメント数B[c]が与えられる。
条件を満たす塗り分けを１つ答えよ。

解法

C≦20なので、A[c]は高々10である。
よってDP[列][1行目のSeg数][2行目][3行目][4行目][5行目][1つ前の列の塗り分け方]=直前の列の状態、でDPすればよい。
各列の塗り分け方はセグメント数がB[c]と一致するものだけを用いる。

最終列まで処理が終わったら、各行のSeg数がA[r]になる物を適当に１つ選び、DPを巻き戻して塗り分け後のグリッドの状態を制限する。

なお、このままだとTLEするので若干の枝刈りが必要。
各行において

• 既にA[r]を超えている
• 残りをどう細かくセグメント分けしてもA[r]に到達しない

ケースを枝刈りしたら1.2s程度で良かった。

…もしかして、幅を半分に割って半分全列挙したらセグメント数5で済むしもっと速い？

int H,W;
int A[30],B[30];
string S[50];
set<int> cand[5];
int p12[6],tar;
map<pair<int,int>,pair<int,int> > from[21];

int ok(int curv,int c) {
	int i;
	FOR(i,H) {
		int seg=curv/p12[i]%12;
		if(seg>A[i]) return 0;
		if(seg+(W-c)/2+2 < A[i]) return 0;
	}
	return 1;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	p12[0]=1;
	FOR(i,5) p12[i+1]=p12[i]*12;
	
	cin>>H>>W;
	FOR(i,H) cin>>A[i], tar += p12[i]*A[i];
	FOR(i,W) cin>>B[i];
	
	FOR(i,1<<H) {
		x=0;
		FOR(y,10) if((i&(1<<y)) && ((i&(1<<(y+1)))==0)) x++;
		cand[x].insert(i);
	}
	
	from[0][make_pair(0,0)]=make_pair(0,0);
	FOR(i,W) {
		FORR(r,from[i]) {
			FORR(c,cand[B[i]]) {
				x = r.first.first;
				FOR(y,H) if((c&(1<<y)) && ((r.first.second&(1<<y))==0)) x += p12[y];
				if(ok(x,i)) from[i+1][make_pair(x, c)]=r.first;
			}
		}
	}
	
	pair<int,int> goal;
	FORR(r,from[W]) if(r.first.first==tar) goal=r.first;
	
	for(x=W-1;x>=0;x--) {
		FOR(y,H) S[y]+=".*"[(goal.second & (1<<y))>0];
		goal=from[x+1][goal];
	}
	
	FOR(y,H) {
		reverse(S[y].begin(),S[y].end());
		cout<<S[y]<<endl;
	}
}

まとめ

本番Hack時にA[r]は8以下にしろと怒られたけど、10セグメントは可能だよね…？