Codeforces #951 : Div2 F. Kostyanych's Theorem

こういうのどこから手を付けるのが良いかよくわからない。
https://codeforces.com/contest/1979/problem/F

問題

N点の完全グラフから、(N-2)辺を取り除いたグラフがある。
以下のクエリをN回まで用いて、ハミルトンパスを1つ構築せよ。

• 整数dを指定すると、次数d以上の点のうち、次数が最小の点で、その中で最小の番号の頂点vを返す。
• 同時に、vと接続されない頂点番号の最小値を返す
• さらに、vとvにつながる辺を削除する。

解法

dequeを使い、再帰的に解く。
次数(N-2)以上の点が1個はあるはずなので、クエリでその点vを求めよう。
残りの(N-1)点からなるパスの両端のどちらかはvとつながるはずなので、再帰的に処理した後、dequeでvを先頭か末尾に追加する。

int T,N,nex[101010];

pair<int,int> ask(int d) {
	cout<<"? "<<d<<endl;
	int x,y;
	cin>>x>>y;
	return {x,y};
}

pair<int,int> hoge(int N) {
	if(N==1) {
		auto p=ask(0);
		return {p.first,p.first};
	}
	if(N==2) {
		auto p=ask(0);
		auto q=ask(0);
		nex[p.first]=q.first;
		return {p.first,q.first};
	}
	
	auto p=ask(N-2);
	int v=p.first;
	int ng=p.second;
	if(ng==0) {
		// N-1頂点
		auto q=ask(0);
		nex[q.first]=v;
		auto ret=hoge(N-2);
		nex[v]=ret.first;
		return {q.first,ret.second};
		
	}
	else {
		auto ret=hoge(N-1);
		if(ng!=ret.first) {
			nex[v]=ret.first;
			return {v,ret.second};
		}
		else {
			nex[ret.second]=v;
			return {ret.first,v};
		}
	}
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) nex[i+1]=-1;
		x=hoge(N).first;
		cout<<"!";
		while(x!=-1) {
			cout<<" "<<x;
			x=nex[x];
		}
		cout<<endl;
	}
}

まとめ

言われてみると簡単なんだけど、それを本番中に考えるのが大変。