Codeforces #403 Div1 D. Axel and Marston in Bitland

こちらも普段のDより簡単。
http://codeforces.com/contest/781/problem/D

問題

N頂点のグラフが与えられる。
このグラフには、P,B2種類のタイプの辺がある。

ここでP,Bからなる文字列Sを考える。
Sは以下のように再帰的に生成する。

• まず最初Sは'P'である。
• SにおけるPとBを反転したものをS'とする。S=S+S'で置き換える。

このグラフにおいて、1番の頂点から始め、時間1毎に隣接点に移動しなければならないとする。
その際、i回目の移動では(1-indexedで)S[i]の種類の辺で移動しなければならない。

さて、このグラフで最適な移動経路を選択した場合、最大何回まで移動可能か。

解法

bit並列とダブリングと二分探索で解く。

まず基本方針としては二分探索で解くことになる。
最大移動回数Mを求めるとき、(2進数で)d桁目より上が定まったとする。ここからさらに2^(d-1)回移動が可能かを考えてみる。
ここでT(d) := Sの先頭2^(d-1)文字、とする。
次にd桁目が0か1か決めたいわけだが、その際dより上の桁の1の数の偶奇により、ここからあと2^(d-1)回移動するとき、T(d)の経路で移動するかT(d)'の経路で移動するかが決まる。

逆に言えば、d桁目が0か1か決めるのはT(d)またはT(d)'の経路で2^(d-1)回移動可能かである。
よって、ダブリングで、各頂点を開始位置としたとき、T(d)またはT(d)'に従い2^(d-1)回移動する経路を求めよう。
移動先の頂点が空でないなら、2^(d-1)回移動可能である。

bit並列でうまく処理すると、ダブリングも二分探索も全体でO(N^2*logM)で計算でき、TLEしない。

int N,M;
bitset<512> ok[512][63][2];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y>>r;
		ok[x-1][0][r][y-1]=1;
	}
	FOR(i,61) FOR(x,N) FOR(y,N) {
		if(ok[x][i][0][y]) ok[x][i+1][0] |= ok[y][i][1];
		if(ok[x][i][1][y]) ok[x][i+1][1] |= ok[y][i][0];
	}
	
	
	bitset<512> cur;
	cur[0]=1;
	int flip=0;
	ll ret=0;
	for(i=60;i>=0;i--) {
		bitset<512> nex;
		FOR(x,N) if(cur[x]) nex |= ok[x][i][flip];
		if(nex.count()) {
			cur=nex;
			ret += 1LL<<i;
			flip ^= 1;
		}
	}
	if(ret>1000000000000000000LL) ret=-1;
	cout<<ret<<endl;
}

まとめ

コードも割と短くて済む。