Codeforces #711 Div2 : E. Two Houses

今回は割とすんなり全完。
https://codeforces.com/contest/1498/problem/E

問題

トーナメントグラフがある。
ただし、入力として与えられるのは頂点数Nと、各頂点vの入次数K[v]のみである。

頂点対A,Bがbi-reachableであるとは、A→BおよびB→Aのパスがともに存在することを意味する。

2頂点A,Bを指定し、A→Bのパスの存在有無を返すクエリが使えるとする。
ただし、1回でもTrueを返すと以後そのクエリは利用できない。
bi-reachableな頂点対A,Bのうち、｜K[A]-K[B]｜が最大となるものを1つ求めよ。

解法

｜K[A]-K[B]｜が大きい順に、(A,B)の対を考える。
その際、K[A]＞K[B]の時、A→Bへのパスの有無をクエリで問い合わせよう。
証明はEditorialに譲るとして、B→Aは必ずパスがある。なので、A→Bにパスがあればそれが解となる。

int N;
int K[505];
int R[505][505];

int ask(int x,int y) {
	cout<<"? "<<(x+1)<<" "<<(y+1)<<endl;
	string s;
	cin>>s;
	return s=="Yes";
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>K[i];
	vector<pair<int,int>> V;
	FOR(y,N) FOR(x,y) V.push_back({abs(K[y]-K[x]),y*1000+x});
	sort(ALL(V));
	reverse(ALL(V));
	
	FORR(v,V) {
		y=v.second/1000;
		x=v.second%1000;
		if(K[x]<K[y]) swap(x,y);
		
		if(ask(x,y)) {
			cout<<"! "<<(x+1)<<" "<<(y+1)<<endl;
			return;
		}
	}
	cout<<"! 0 0"<<endl;
	
	
	
}

まとめ

本番よくこれすんなり思いつけたな。