kmjp's blog

競技プログラミング参加記です

AtCoder AGC #017 : F - Zigzag

これ系の計算量削減テク、いつも思いつかない。
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ずつ上下に移動する問題(括弧列問題など)とかでよくこんな感じの状態圧縮テクが出るイメージ。