kmjp's blog

競技プログラミング参加記です

Good Bye 2016 : F. New Year and Finding Roots

これはなかなか面白かった。
http://codeforces.com/contest/750/problem/F

問題

高さHの完全二分木がある。
各頂点には1~(2^H-1)のいずれかの整数が1つずつ書かれている。

初期状態として木の構成はHしか与えられない。
ここで、番号を与えるとその番号が書かれた頂点の隣接頂点に書かれた番号の一覧を返すクエリを使い、根頂点に書かれた番号を求めたい。
クエリを16回以内で利用し、根頂点の番号を求めよ。

解法

適当な頂点から、2方向に向かって葉にぶつかるまで隣接頂点をたどる。
途中次数が2の点があればそれが根である。以下根が見つからなかった場合について示す。

2つの葉がわかれば、その葉を結ぶパスの中点が最も根に近い。
よって、その中点から未訪問の隣接点(=中点の親頂点)方向再度探索し、葉を見つけては最も根に近い頂点を求める、を繰り返す。
ただし、これを繰り返すと最悪21回クエリを投げることになる。

もし途中で中点の深さが3以下になるタイミングがあったとする。(最大でもクエリ10回以内にこの状態になる)
その親の深さは2以下なので、あとはそこから距離2までの未訪問頂点に対しクエリを出せば、根が見つかる。
この最後のステップは最大1+2+4で7回クエリを実行するので、合計で17回クエリを実行することになり条件をオーバーする。
ただ、親頂点から距離2の頂点4つに根があることは確実なので、1+2+3で6回クエリを実行した時点で根が見つからなければ最後の頂点を根とみなしてよい。

int T,H;
vector<int> nei[200];
vector<int> path;
int HH[200];
int root;


void ask(int v) {
	if(nei[v].size()) return;
	
	int n,x;
	cout<<"? "<<v<<endl;
	cin>>n;
	if(n==2) root=v;
	while(n--) cin>>x, nei[v].push_back(x);
	
}

int dfs(int cur,vector<int>& P) {
	ask(cur);
	P.push_back(cur);
	if(nei[cur].size()<=2) return 1;
	FORR(r,nei[cur]) if(r!=P[P.size()-2]) return dfs(r,P);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>H;
		root=0;
		FOR(i,200) nei[i].clear(),HH[i]=0;
		
		vector<int> P,Q;
		int par;
		ask(1);
		if(nei[1].size()==2) {
			goto out;
		}
		else if(nei[1].size()==1) {
			HH[1]=H;
			P.push_back(1);
		}
		else if(nei[1].size()==3) {
			P.push_back(1);
			dfs(nei[1][0],P);
			reverse(ALL(P));
			Q.push_back(1);
			dfs(nei[1][1],Q);
			if(root) goto out;
			for(i=1;i<Q.size();i++) P.push_back(Q[i]);
			FOR(i,P.size()/2+1) HH[P[i]]=HH[P[P.size()-1-i]]=H-i;
			P.resize(P.size()/2+1);
		}
		
		int nex;
		while(HH[P.back()]>4) {
			FORR(r,nei[P.back()]) if(HH[r]==0) nex=r;
			Q.clear();
			Q.push_back(P.back());
			dfs(nex,Q);
			if(root) goto out;
			
			for(i=1;i<Q.size();i++) P.push_back(Q[i]);
			FOR(i,P.size()/2+1) HH[P[i]]=HH[P[P.size()-1-i]]=H-i;
			P.resize(P.size()/2+1);
		}
		
		if(root) goto out;
		
		
		FORR(r,nei[P.back()]) if(HH[r]==0) nex=r;
		HH[nex]=HH[P.back()]-1;
		if(HH[nex]==1) {
			root=nex;
		}
		else {
			vector<int> cand;
			
			ask(nex);
			if(HH[nex]==2) {
				FORR(x,nei[nex]) if(HH[x]==0) cand.push_back(x);
			}
			else if(HH[nex]==3) {
				FORR(x,nei[nex]) if(HH[x]==0) {
					HH[x]=1;
					ask(x);
					FORR(r,nei[x]) if(HH[r]==0) cand.push_back(r);
				}
			}
			root=cand.back();
			cand.pop_back();
			FORR(x,cand) ask(x);
		}
out:
		cout<<"! "<<root<<endl;
	}
}

まとめ

これは本番解けたかもしれないなぁ。
Eを捨てて取り組んでもよかったかも。