Codeforces #523 Div2 F. Lost Root

こっちもすんなり。
http://codeforces.com/contest/1061/problem/F

問題

N頂点からなる完全K分木がある。(N,Kは最初に与えられる。)
ただし1～Nのどのラベルがどこにくるかはわからない。
この木の根を求めたい。

3頂点a,b,cを指定すると、a-cのパス上にbがあるかどうかを返すクエリがある。
このクエリを60N回まで使い、木の根に相当する頂点のラベルを求めよ。

解法

完全K分木なので、N頂点の過半数は葉である。
よって、最初に2頂点対を乱拓し、根がパス上に来るような2つの葉(u,v)を求めよう。
木の深さをDとすると、残り(N-2)頂点中(2*D-1)頂点が(u,v)上に来るので、1回あたり(N-2)回クエリを使えば確認できる。

(u,v)およびパス(u,v)上の点が求められたら、あとはそのパス上の頂点の3つ組を総当たりしてクエリに掛ければ、パスの中央となる点、すなわち木の根を特定できる。

int N,K,D;

bool ask(int a,int b,int c) {
	cout<<"? "<<a<<" "<<b<<" "<<c<<endl;
	cout.flush();
	string s;
	cin>>s;
	return s=="Yes";
}

void ans(int v) {
	cout<<"! "<<v<<endl;
	exit(0);
}

vector<int> getnum(int a,int b) {
	vector<int> V;
	int i;
	for(i=1;i<=N;i++) {
		if(i!=a && i!=b && ask(a,i,b)) V.push_back(i);
	}
	return V;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	int cur=1,sum=0;
	while(sum<N) {
		D++;
		sum+=cur;
		cur*=K;
	}
	
	srand(time(NULL));
	vector<int> V;
	while(1) {
		x=rand()%N+1;
		while(1) {
			y=rand()%N+1;
			if(x!=y) break;
		}
		
		V=getnum(x,y);
		if(V.size()==2*D-3) break;
	}
	
	int tar=(V.size()-1)/2*(V.size()-1)/2;
	FORR(a,V) {
		int num=0;
		FORR(b,V) if(a!=b) {
			FORR(c,V) if(a!=c && c>b) num+=ask(b,a,c);
		}
		
		if(num==tar) ans(a);
	}
	
}

まとめ

シンプルな設定で良かった。