CSAcademy Round #16 : E. Tree Node Distances

これは面白かった。
https://csacademy.com/contest/round-16/#task/tree-node-distances

問題

根付き木を成すグラフ上に、２つの頂点を指すポインタA,Bがある。
以下のクエリを用いてA,Bが初期状態で指す頂点間の距離Dを求めよ。
なお、クエリは20*D回までしか利用できない。

• どちらかのポインタの指す頂点を１つ親に動かす。すでに根を指している場合、その旨が返る。
• ２つのポインタが同じ頂点を指しているか判定する。
• どちらかのポインタの指す頂点を初期位置に戻す。

解法

A,Bが指す頂点のLCAを求められれば、あとはA-LCAとLCA-Bの距離を足せばよいので容易である。
ただ、両頂点の深さを求めようとしてもうまくいかない。
クエリの回数制限の都合上、A,BからLCAが近く、根が遠い場合根までの距離を求められない。

よくよく考えると、両頂点の深さを厳密に求める必要はなく、両者の深さの差がわかればいいことがわかる。
深さの差がわかれば、深さが一致するまで深いほうのポインタを親に動かしていき、その後それぞれ親方向にポインタを１個ずつ動かしながら一致判定すればいずれLCAに到達する。

では両頂点の深さの差をどう求めるか。
Aを1個親に動かし、Bを2個親に動かし、Aを4個親に動かし、Bを8個親に動かし…と両ポインタを交互に移動距離を倍々しながら親をたどりつつ、もう一つのポインタと位置が一致しないか判定する。
こうすると初期状態でAとBどちらが深くても、いずれ両者はどこかで一致する。
またその際必要なクエリはDの数倍程度に収まる。

int FA,FB;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	FOR(i,100) {
		FOR(x,1<<i) {
			if(i%2==0) {
				cout<<"F A"<<endl;
				cin>>y;
				if(y) FA++;
			}
			else {
				cout<<"F B"<<endl;
				cin>>y;
				if(y) FB++;
			}
			cout<<"E"<<endl;
			cin>>y;
			if(y) goto out;
			
		}
	}
	out:
	
	ll ret=0;
	cout<<"R A"<<endl;
	cout<<"R B"<<endl;
	while(FA>FB) {
		cout<<"F A"<<endl;
		cin>>y;
		FA--;
		ret++;
	}
	while(FA<FB) {
		cout<<"F B"<<endl;
		cin>>y;
		FB--;
		ret++;
	}
	
	while(1) {
		cout<<"E"<<endl;
		cin>>x;
		if(x) break;
		cout<<"F A"<<endl;
		cin>>x;
		cout<<"F B"<<endl;
		cin>>x;
		ret+=2;
	}
	cout<<"A "<<ret<<endl;
	
}

まとめ

面白かった。よくこれ思いつけたな…。