なんとか本番解けた。
http://codeforces.com/contest/534/problem/F
問題
R*Cの2次元グリッドの各セルを白黒で塗り分けたい。
1つの列または行で連続した黒セルを1セグメントとカウントするとき、各行rのセグメント数A[r]及び各列cのセグメント数B[c]が与えられる。
条件を満たす塗り分けを1つ答えよ。
解法
C≦20なので、A[c]は高々10である。
よってDP[列][1行目のSeg数][2行目][3行目][4行目][5行目][1つ前の列の塗り分け方]=直前の列の状態、でDPすればよい。
各列の塗り分け方はセグメント数がB[c]と一致するものだけを用いる。
最終列まで処理が終わったら、各行のSeg数がA[r]になる物を適当に1つ選び、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セグメントは可能だよね…?