これも割とすんなり解いているな。
https://atcoder.jp/contests/past202010-open/tasks/past202010_n
問題
18x6のグリッドを0/1で埋めることを考える。初期状態で各セルは0/1/?のいずれかである。
?の部分をそれぞれ0/1のいずれかで埋めたとき、以下を満たす組み合わせは何通りか。
- 各マスの値は、そのマスと上下左右のマスの5値の中央値に等しい。
解法
上2行分の値をbitmaskで持ちながらDPしていく。
上2行の値が定まると、次の行に取りえる選択肢がかなり狭まるので、あらかじめ選択肢を列挙しておくとTLEせずに済む。
vector<int> ok[1<<6][1<<6]; ll from[1<<6][1<<6]; ll to[1<<6][1<<6]; void solve() { int i,j,k,l,r,x,y; string s; int m1,m2,m3; FOR(m1,1<<6) FOR(m2,1<<6) FOR(m3,1<<6) { int c=1; FOR(y,6) { x=0; x+=(m1>>y)&1; x+=(m3>>y)&1; x+=(m2>>y)&1; x+=(m2>>(y+1))&1; if(y) x+=(m2>>(y-1))&1; if(x>=3&&(m2&(1<<y))==0) c=0; if(x<3&&(m2&(1<<y))) c=0; } if(c) ok[m1][m2].push_back(m3); } FOR(m1,1<<6) from[0][m1]=1; FOR(i,18) { ZERO(to); cin>>s; FOR(m2,1<<6) { int c=1; FOR(y,6) { if(s[y]=='0'&&((m2>>y)&1)) c=0; if(s[y]=='1'&&((m2>>y)&1)==0) c=0; } if(c==0) continue; FOR(m1,1<<6) FORR(p,ok[m1][m2]) to[m2][p]+=from[m1][m2]; } swap(from,to); } ll ret=0; FOR(m1,1<<6) ret+=from[m1][0]; cout<<ret<<endl; }
まとめ
これなんで縦横の幅固定にしてるんだろうな。