これは面白かった。
https://csacademy.com/contest/round-16/#task/tree-node-distances
問題
根付き木を成すグラフ上に、2つの頂点を指すポインタA,Bがある。
以下のクエリを用いてA,Bが初期状態で指す頂点間の距離Dを求めよ。
なお、クエリは20*D回までしか利用できない。
- どちらかのポインタの指す頂点を1つ親に動かす。すでに根を指している場合、その旨が返る。
- 2つのポインタが同じ頂点を指しているか判定する。
- どちらかのポインタの指す頂点を初期位置に戻す。
解法
A,Bが指す頂点のLCAを求められれば、あとはA-LCAとLCA-Bの距離を足せばよいので容易である。
ただ、両頂点の深さを求めようとしてもうまくいかない。
クエリの回数制限の都合上、A,BからLCAが近く、根が遠い場合根までの距離を求められない。
よくよく考えると、両頂点の深さを厳密に求める必要はなく、両者の深さの差がわかればいいことがわかる。
深さの差がわかれば、深さが一致するまで深いほうのポインタを親に動かしていき、その後それぞれ親方向にポインタを1個ずつ動かしながら一致判定すればいずれ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; }
まとめ
面白かった。よくこれ思いつけたな…。