yukicoder : No.3237 Find the Treasure!

本番ちょっと間に合わず…。
https://yukicoder.me/problems/no/3237

問題

N点の無向グラフが与えられる。
このうち、以下のクエリを15回まで用いて、お宝のある1点を特定するインタラクティブ問題である。

各クエリでは、(N-1)本の各辺の両端のいずれかの点を指定する(同じ点を複数回指定してもよい)。
その後、その中にお宝のある点が含まれるかどうかを教えてくれる。

解法

適当な根に対し根付き木とし、初手では深さの偶奇によって各点をクエリに入れるか入れないか分類しよう。
これにより、まずお宝のある深さの偶奇がわかる。
以後のクエリにおいて、各辺に対し確実にお宝が存在しない側を指定することができるようになる。

そこで、あとはお宝のありうる点の候補をクエリごとに半々に絞り込んでいこう。

int N;
vector<int> E[101010];
int U[101010],V[101010];
int D[101010];

void dfs(int cur,int pre,int d) {
	D[cur]=d;
	FORR(e,E[cur]) if(e!=pre) dfs(e,cur,d^1);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>U[i]>>V[i];
		E[U[i]].push_back(V[i]);
		E[V[i]].push_back(U[i]);
	}
	dfs(1,1,0);
	
	cout<<"?";
	FOR(i,N-1) {
		if(D[U[i]]) cout<<" "<<V[i];
		else cout<<" "<<U[i];
	}
	cout<<endl;
	
	cin>>s;
	vector<int> cand;
	if(s=="Yes") {
		FOR(i,N-1) {
			if(D[U[i]]==0) cand.push_back(U[i]);
			else cand.push_back(V[i]);
		}
	}
	else {
		FOR(i,N-1) {
			if(D[V[i]]==0) cand.push_back(U[i]);
			else cand.push_back(V[i]);
		}
	}
	FOR(i,14) {
		set<int> X[2];
		FOR(j,cand.size()) X[j%2].insert(cand[j]);
		cout<<"?";
		FOR(j,N-1) {
			if(X[0].count(U[j])) {
				cout<<" "<<U[j];
			}
			else if(X[0].count(V[j])) {
				cout<<" "<<V[j];
			}
			else if(X[1].count(U[j])) {
				cout<<" "<<V[j];
			}
			else if(X[1].count(V[j])) {
				cout<<" "<<U[j];
			}
			else {
				cout<<" "<<U[j];
			}
		}
		cout<<endl;
		cin>>s;
		cand.clear();
		FORR(x,X[s=="No"]) cand.push_back(x);
	}
	cout<<"! "<<cand[0]<<endl;
	
		
}

まとめ

これは割とすんなり思いつけた。