これ系の計算量削減テク、いつも思いつかない。
http://agc017.contest.atcoder.jp/tasks/agc017_f
問題
正三角形状に頂点が並んでいる。
頂点はN段あり、i段目にはi個の頂点が並んでいる。
a段目で左からb個目の頂点を(a,b)とする。
(a,b)から(a+1,b)または(a+1,b+1)のいずれかに線を引くことを繰り返し、(1,1)→(N,*)まで(N-1)回引いた線を連結したものを考える。
このような線をM個引きたい。
ただしk回目に引く線は、(k-1)回目に引く線の左側に来てはならない。
また一部の線は(a,b)から(a+1,b)と(a+1,b+1)どちらに線を引くか固定されている。
線の引き方は何通りあるか。
解法
線の引き方の固定は単なる埋め込み防止措置なので、あまり考えなくてよい。
まずは以下のbitDPを考える。
dp(k,mask) := k本目まで線を引いた際、k本目の線の引き方がmaskで表されるケースの組み合わせ数
maskはi回目の移動で右側に移動したときi bit目が立つとする。
dp(k-1,mask)→dp(k,mask')の遷移は、任意のbit数でmaskのsuffixよりmask'のsuffixが小さくなければ可能である。
ただmaskとmask'を総当たりすると計算量がO(M*4^M)かかり問題外である。
k本目の線のうちl段目まで線を引いた状態を考える。
dp(k,l,w,mask,mask') := k本目のうちl段目まで線を引いたところ、(k-1)本目の線との距離がwで、l段目までの移動経路がmaskで、(k-1)本目のl段目以降の移動経路がmask'であるような組み合わせ
dp(k,l,w,mask,mask')から(l+1)段目までの線の引き方を左右2通り考えてdp(k,l+1,w',mask2,mask2')を更新していこう。
maskとmask'のビット数は合わせて2^Mなので、計算量はO(N^3*2^M)ありまだちょっと多い。
wを考慮しなくて済むようにすることを考えよう。
wが正であるということは、あとで(k-1)本目が1回右側に移動しても問題ないことに相当する。
よってwが1増える(mask'の現在のビットが左に線を引いたことを示しており、今k本目の線は右に線を引こうとしている)場合、mask2'のうちl段目以降の最初のビットを落とせば帳尻があう。
この作業はビット演算を行えばO(1)である。またwを考慮しなくてよくなり状態が減るのでO(N^2*2^M)となる。
int N,M,K; int path[21][21]; int from[1<<19]; int to[1<<19]; ll mo=1000000007; int add(int& a,int& b) { a+=b; if(a>=mo) a-=mo; return a; } void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M>>K; FOR(x,N) FOR(y,M+1) path[y][x]=3; N--; FOR(i,K) { cin>>x>>y>>j; path[x][y-1]=1<<j; } from[0]=1; for(int line=1;line<=M;line++) { for(int step=0;step<N;step++) { int sm=1<<step; ZERO(to); FOR(i,1<<N) if(from[i]) { if(path[line][step]&1) { if((i&sm)==0) add(to[i],from[i]); } if(path[line][step]&2) { if((i&sm)==0) { if(i<sm) add(to[i^sm],from[i]); else add(to[((i-sm)&i) | sm],from[i]); } else add(to[i],from[i]); } } swap(from,to); } } ll ret=0; FOR(i,1<<N) ret+=from[i]; cout<<ret%mo<<endl; }
まとめ
1ずつ上下に移動する問題(括弧列問題など)とかでよくこんな感じの状態圧縮テクが出るイメージ。