バグが取り切れず時間内に終わらなかった。
https://atcoder.jp/contests/abc379/tasks/abc379_g
問題
H*Wのグリッドがあり、一部のマスには1~3の数字が入っている。
全マスに1~3のいずれかの数字を入れるとき、隣接マスに同じ数字が入らないような入れ方は何通りか。
解法
H<Wなら先に90度回転するなどしてW≦Hにしておく。
row-major order順で値を埋めて行くが、その際各列確定済みの最下段の数値を状態として持とう。
一見3^W通り状態がありそうだが、隣接マスには同じ数字が入らないので高々3^2*2^(W-2)通りの状態で済む。
あとは、各マス、上と左の値を見ながら同じ数字が隣接しないように埋めて行く。
int H,W; string V[200]; string S[200]; const ll mo=998244353; ll p10[18]; vector<int> decode(int first,int mask) { int i; vector<int> V={first}; FOR(i,W-1) V.push_back((V.back()+1+(mask>>i)%2)%3); return V; } void solve() { int i,j,k,l,r,x,y; string s; cin>>H>>W; FOR(y,H) cin>>V[y]; if(W>H) { FOR(y,H) FOR(x,W) S[x].push_back(V[y][x]); swap(W,H); } else { FOR(y,H) S[y]=V[y]; } p10[0]=1; FOR(i,16) p10[i+1]=p10[i]*10; map<ll,ll> F,T; F[0]=1; FOR(y,H) { FOR(x,W) { T.clear(); FORR2(a,b,F) { ll p=a/p10[W-1-x]%10; ll q=a/p10[W-x]%10; for(j=1;j<=3;j++) { if(S[y][x]!='?'&&S[y][x]!='0'+j) continue; if(j==p||j==q) continue; ll na=a+(j-p)*p10[W-1-x]; (T[na]+=b)%=mo; } } swap(F,T); } } ll ret=0; FORR2(a,b,F) ret+=b; cout<<ret%mo<<endl; }
まとめ
雑に10進法で状態を持っても間に合ったのか…。
うまく状態をシリアルな数値にencodeしようとしてバグを作りこんでしまった。