Codeforces #889 : Div1 D. Michael and Hotel

これは全く方針を思いつかなかったな。
https://codeforces.com/contest/1854/problem/D

問題

N頂点の有向グラフがある。
有向辺u→a[u]は明には与えられない。

クエリでは、整数u,v及び整数集合Sを指定する。
頂点uから辺に沿ってv回移動したとき、その頂点がSに含まれるかを尋ねることができる。

このクエリを高々4N回使い、以下の集合Aを求めよ。

• 頂点番号1番から辺に沿って移動する人と、頂点番号v∈Aから辺に沿って移動する人が合流可能

解法

u→a[u]に辺を張ったFunctionグラフを考える。
u=1から辺に沿って移動する閉路を考えると、同じ閉路に遷移可能なv∈Aが解となる。

まず、u=1からN+i回移動した先を求めよう。
Sを二分探索することで、移動1回につきO(logN)回のクエリで移動先を特定できる。
N回以上移動すると閉路に落ち込むので、i=1～kまで走査すると閉路中のk要素を特定できる。

次に、各頂点vについて、N+nk回移動させてみて、このk要素に到達するか試そう。
nk≦Nの範囲でnを動かせばよい。またk=63とすると総クエリ回数を抑えられる。

int N;

int ask(int u,int k,set<int> V) {
	cout<<"? "<<(u+1)<<" "<<k<<" "<<V.size();
	FORR(v,V) cout<<" "<<v+1;
	cout<<endl;
	cin>>u;
	return u;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	set<int> ok;
	cin>>N;
	FOR(i,63) {
		int L=0,R=N;
		while(L+1<R) {
			int M=(L+R)/2;
			set<int> A;
			for(j=L;j<M;j++) A.insert(j);
			if(ask(0,N+i,A)) R=M;
			else L=M;
		}
		ok.insert(L);
	}
	if(ok.size()==63) {
		for(k=63;k<=N*2;k*=2) {
			if(ok.size()<k){
				FOR(i,N) if(ok.count(i)==0) {
					if(ask(i,N,ok)) ok.insert(i);
				}
				break;
			}
			FOR(i,N) if(ok.count(i)==0) {
				if(ask(i,k,ok)) ok.insert(i);
			}
		}
	}
	else {
		FOR(i,N) if(ok.count(i)==0) {
			if(ask(i,101010,ok)) ok.insert(i);
		}
	}
	cout<<"! "<<ok.size();
	FORR(v,ok) cout<<" "<<v+1<<endl;
	
}

まとめ

これは思いつかなかったな…。