yukicoder : No.2085 Directed Complete Graph

このテクどこかで見たな…。
https://yukicoder.me/problems/no/2085

問題

N頂点のトーナメントグラフがある。
最大4000回まで、辺を指定してその向きを問うことができる。
このグラフの最長パスを1つ求めよ。

解法

トーナメントグラフは必ずハミルトンパスを持つ。
そこで、マージテクの要領で、部分グラフにおけるハミルトンパスを連結していこう。
2つのパスS[0]→S[1]....とT[0]→T[1]→…を連結することを考える。
S[0]とT[0]の向きを調べ、S[0]→T[0]なら、連結したハミルトンパスの先頭はS[0]とし、その後S[1]....とT[0]....を同様に連結する作業を繰り返す。
S[0]→S[1]、S[0]→T[0]の向きに辺があることがわかっているので、S[0]の次にS[1]とT[0]どちらが来ても問題ない。

int N;

queue<int> merge(int L,int R) {
	queue<int> V;
	if(L+1==R) {
		V.push(L);
		return V;
	}
	auto P=merge(L,(L+R)/2);
	auto Q=merge((L+R)/2,R);
	
	while(P.size()||Q.size()) {
		if(P.empty()) {
			V.push(Q.front());
			Q.pop();
		}
		else if(Q.empty()) {
			V.push(P.front());
			P.pop();
		}
		else {
			cout<<"? "<<P.front()<<" "<<Q.front()<<endl;
			int r;
			cin>>r;
			if(r==1) {
				V.push(P.front());
				P.pop();
			}
			else {
				V.push(Q.front());
				Q.pop();
			}
		}
	}
	return V;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	auto p=merge(1,N+1);
	cout<<"!"<<endl;
	cout<<p.size()-1<<endl;
	while(p.size()) {
		cout<<p.front()<<" ";
		p.pop();
	}
	cout<<endl;
}

まとめ

Codeforcesで見たんだっけかな。