Codeforces #716 Div2 : E. Baby Ehab's Hyper Apartment

なんかDiv2の最終問題にinteractive多いイメージがあるな。
https://codeforces.com/contest/1514/problem/E

問題

N頂点のトーナメントグラフを特定するinteractive問題である。
以下のクエリを用いて、各頂点a-b間でa→bに至るパスがあるかを求めよ。

• 2頂点a,bを指定すると、a-b間の辺の向きを答える。このクエリは9N回まで利用できる。
• 頂点xと、頂点集合Sを指定すると、xからSのいずれかの頂点に到達可能かを答える。このクエリは2N回まで利用できる。

解法

トーナメントグラフは、必ずハミルトンパスがある。
そこで、マージソートの要領で２パスを連結して新たなパスを作る作業を繰り返し、まず1つハミルトンパスを作ろう。
これはO(NlogN)回程度前者のクエリを用いればよい。

あとはハミルトンパス上の各点から、どのぐらいハミルトンパスをさかのぼることができるかを後者のクエリで求めて行く。
これは尺取り法の要領でO(N)回後者のクエリを用いればよい。

int T,N;
int E[101][101];

int ask(int a,int b) {
	int x;
	cout<<"1 "<<a<<" "<<b<<endl;
	cin>>x;
	return x;
}

int ask2(int a,vector<int> b) {
	cout<<"2 "<<a<<" "<<b.size();
	sort(ALL(b));
	FORR(c,b) cout<<" "<<c;
	cout<<endl;
	cin>>a;
	return a;
	
}

vector<int> merge(vector<int> A,vector<int> B) {
	vector<int> R;
	reverse(ALL(A));
	reverse(ALL(B));
	while(A.size()&&B.size()) {
		if(ask(A.back(),B.back())) {
			R.push_back(A.back());
			A.pop_back();
		}
		else {
			R.push_back(B.back());
			B.pop_back();
		}
	}
	while(A.size()) R.push_back(A.back()), A.pop_back();
	while(B.size()) R.push_back(B.back()), B.pop_back();
	return R;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		
		queue<vector<int>> V;
		FOR(i,N) V.push({i});
		while(V.size()>=2) {
			auto a=V.front();
			V.pop();
			auto b=V.front();
			V.pop();
			
			V.push(merge(a,b));
		}
		vector<int> W=V.front();
		
		ZERO(E);
		int cur=N-1;
		for(i=N-1;i>=0;i--) {
			cur=min(cur,i);
			while(cur) {
				vector<int> C;
				FOR(j,cur) C.push_back(W[j]);
				if(ask2(W[i],C)==0) break;
				cur--;
			}
			for(j=cur;j<N;j++) E[W[i]][W[j]]=1;
		}
		FOR(k,N) FOR(x,N) FOR(y,N) E[x][y]|=E[x][k]&E[k][y];
		
		cout<<3<<endl;
		FOR(y,N) {
			FOR(x,N) cout<<E[y][x];
			cout<<endl;
		}
		cin>>x;
	}
}

まとめ

これは思いつかなかった…。
「トーナメントグラフは、必ずハミルトンパスがある。」を知らないとダメだな。