Codeforces #682 Div2 F. Olha and Igor

この考察パートは賢いな…。
https://codeforces.com/contest/1438/problem/F

問題

高さHの完全二分木を考える。
ノード数をNとすると、各ノードに振られたラベルは、1～NのPermutationとなっている。

以下のクエリをN+420回まで利用し、根ノードに振られたラベルを求めよ。

• 3つのラベルu,v,wを指定する。ラベルwのノードを根としたとき、LCA(u,v)を答える。

解法

ランダムなu,v,wでクエリを何度も実行すると、答えの最頻値上位2個が根ノード直下の子頂点となる。
この頂点のラベルをx,yとする。
他の全ノードiに対し、x,y,iをクエリとして実行すると、結果がiとなるのはiが根ノードのラベルの時だけである。

int N,H;
int C[1<<19];

int ask(int u,int v,int w) {
	cout<<"? "<<u<<" "<<v<<" "<<w<<endl;
	cin>>u;
	return u;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H;
	N=(1<<H)-1;
	FOR(i,410) {
		while(1) {
			x=rand()%N+1;
			y=rand()%N+1;
			r=rand()%N+1;
			if(x!=y&&x!=r&&y!=r) break;
		}
		C[ask(x,y,r)]++;
	}
	vector<pair<int,int>> V;
	FOR(i,N) V.push_back({C[i+1],i+1});
	sort(ALL(V));
	x=V.back().second;
	y=V[V.size()-2].second;
	FOR(i,N) if(i+1!=x&&i+1!=y) {
		r=ask(x,y,i+1);
		if(r!=x&&r!=y) {
			cout<<"! "<<r<<endl;
			return;
		}
	}
	
}

まとめ

この特徴、使うことあるかな…。