Codeforces #948 : Div2 E. Tensor

うーむ。
https://codeforces.com/contest/1977/problem/E

問題

以下のN頂点の有向グラフがある。

• 辺の向きは、頂点番号の大きい方から小さい方のみである。
• 3頂点i,j,kを選ぶと、j→i、k→i、k→jの少なくとも1個はパスがある。

ここで、頂点を白黒に塗るとき、同色の頂点対は、片方から片方にパスが存在するようにしたい。

以下のクエリを2N回まで使い、条件を満たす彩色をせよ。

• 2点を指定すると、片方から片方にパスが存在するかを返す。

解法

番号の小さい順に定めて行く。
その際、途中経過として白・黒の他赤色の点を導入する。
白と黒の頂点番号最大の点は、相互にパスが張れない状態をキープすることとする。
赤頂点は、白と黒の頂点番号最大の点のどちらにもパスを張れる点の集合とする。

• n番目の頂点まで色が定まり、(n+1)晩、絵の頂点を考えるとする。
• もし白・黒のうち存在しない色があれば、とりあえずその色にする。
• 赤い点がない場合
  • もし(n+1)番の点から、白黒両方の番号最大の点にパスがあるなら、(n+1)番はいったん赤色にしておく。
  • もし(n+1)番の点から、白黒のうちの番号最大の点にパスがあるなら、(n+1)番はその色に合わせる。
  • 白黒の点の条件より、どちらにもパスが張れないことはない。
• 赤い点がある場合
  • もし(n+1)番の点から、赤い頂点番号最大の点にパスがあるなら、(n+1)番は赤色にしておく。
  • そうでない場合、白か黒のどちらかの番号最大の点にパスが張れるはずである。その場合、(n+1)番の点はその色にしつつ、赤い点はすべて白黒反対の色にする。

上記を繰り返せば、1頂点あたり2クエリで色を決められる。

int T;
int N;
int ask(int i,int j) {
	string s;
	cout<<"? "<<i+1<<" "<<j+1<<endl;
	cin>>s;
	return s=="YES";
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		vector<int> A,B,C;
		
		cin>>N;
		A={0};
		for(i=1;i<N;i++) {
			if(C.size()) {
				if(ask(C.back(),i)) {
					C.push_back(i);
				}
				else if(ask(A.back(),i)) {
					FORR(c,C) B.push_back(c);
					A.push_back(i);
					C.clear();
				}
				else {
					FORR(c,C) A.push_back(c);
					B.push_back(i);
					C.clear();
				}
			}
			else if(B.empty()) {
				if(ask(A.back(),i)) {
					A.push_back(i);
				}
				else {
					B.push_back(i);
				}
			}
			else {
				x=ask(A.back(),i);
				y=ask(B.back(),i);
				if(x&&y) C.push_back(i);
				else if(x) A.push_back(i);
				else B.push_back(i);
			}
		}
		int D[102]={};
		FORR(b,B) D[b]=1;
		
		cout<<"! ";
		FOR(i,N) cout<<D[i]<<" ";
		cout<<endl;
	}
	
}

まとめ

シンプルで良い問題。