こちらもしょうもなさすぎるミスした。
https://community.topcoder.com/stat?c=problem_statement&pm=16399&rd=18188
問題
R*Cのグリッドのうち、いくつかを選択したい。
その際、以下の状態は不可である。
- 選択したセルが隣接する
- あるセルが、2個以上の選択したセルが隣接する
条件を満たす選択の仕方で、B個以上のセルを選択しているのは何通りか。
解法
まず横幅が縦より短くなるように回転させておく。そうするとCは13以下となる。
あとは上の行から、各セルが
- 未選択かつ隣接セルに選択マスなし
- 未選択かつ隣接セルに選択マスが1つ
- 選択済み
で最大(3^C)通りと、さらに選択済みのマスの数からなる各状態に対し、次の行の状態を(2^C)通り総当たりしよう。
実際には選択済みのマスは連続できないので、もう少し総当たりの総数は減る。
以下のコードでは、事前に(3^C)通りのうちあり得る状態と、次の行で取れる(2^C)通りのうち有効なものに対して、次の行の状態を列挙して高速化している。
ll from[4063][70]; ll to[4063][70]; map<int,int> T; const ll mo=1000000007; class BasePlacement { public: int count(int R, int C, int B) { if(C>R) swap(R,C); vector<int> cand; vector<int> state; int i; int mask; FOR(mask,1<<C) { if(mask&(mask<<1)) continue; if(mask&(mask<<2)) continue; cand.push_back(mask); } FORR(a,cand) FORR(b,cand) { if(a&b) continue; if((a<<1)&b) continue; if(a&(b<<1)) continue; int i; int mask2=0; int c=1; FOR(i,C) { if(b&(1<<i)) { mask2+=2*c; } else { int num=0; if(b&(2<<i)) num++; if(i&&(b&(1<<(i-1)))) num++; if(a&(1<<i)) num++; assert(num<=1); mask2+=num*c; } c*=3; } state.push_back(mask2); } cout<<cand.size()<<endl; cout<<state.size()<<endl; sort(ALL(state)); state.erase(unique(ALL(state)),state.end()); vector<vector<pair<int,int>>> nex; nex.resize(state.size()); int j; T.clear(); FOR(j,state.size()) T[state[j]]=j; FOR(j,state.size()) { int s=state[j]; FORR(c,cand) { int p=1; int t=0,add=0; FOR(i,C) { int cur=s/p%3; if(cur==2) { if(c&(1<<i)) break; if(c&(2<<i)) break; if(i&&(c&(1<<(i-1)))) break; add+=p; } else if(cur==1) { if(c&(1<<i)) break; int num=0; if(c&(2<<i)) num++; if(i&&(c&(1<<(i-1)))) num++; add+=p*num; } else { if(c&(1<<i)) { add+=2*p; t++; } else { int num=0; if(c&(2<<i)) num++; if(i&&(c&(1<<(i-1)))) num++; add+=p*num; } } p=p*3; } if(i==C) { nex[j].push_back({T[add],t}); } } } ZERO(from); from[T[0]][0]=1; int x,y; FOR(y,R) { FOR(i,state.size()) FOR(x,R*C/3+3) to[i][x]=0; FOR(i,state.size()) FOR(x,R*C/3+3) if(from[i][x]) { FORR(n,nex[i]) { (to[n.first][x+n.second]+=from[i][x])%=mo; } } swap(from,to); } ll ret=0; FOR(i,state.size()) for(j=B;j<=69;j++) ret+=from[i][j]; return ret%mo; } }
まとめ
いろいろ前処理やったおかげで1s以下で余裕で通るが、オーバースペックだったかも。