Codeforces #649 Div2 E. X-OR

CodeforcesのECRやDiv2、時々妙なInteractive入るよなぁ。
https://codeforces.com/contest/1364/problem/E

問題

0～(N-1)のPermutation Pを当てるinteractive問題である。
2要素を指定すると、両者のorを教えてもらえる。
このクエリを2N+160回ほど使って、全要素を特定せよ。

解法

0の位置を特定できれば、後は(N-1)回クエリを使い、全要素特定できる。

まず、各bitについて0である要素を求めよう。
各bitが立つ確率は半分以下なので、乱択でもlog(N)要素求めるのにおよそ2log(N)回ぐらいで済むことが期待できる。

ここでP[x]=0となるxを求めたいわけだが、初期値x=0(P[x]=0とは限らない)として、y=1から候補を総当たりしていこう。
仮にP[x] or P[y] = P[x]となる場合、P[y]はP[x]より小さい。
このようなyを見つけたら、上記各bitが0である要素とのorを取ると、P[y]の値を特定できる。
そしてx=yと更新しよう。

Nは高々2進数で11桁なので、xを更新する回数は11回以下だし、各bitを求める処理と合わせて121回のクエリで済む。
最初の乱択を含めて160回ぐらいでどうにかなる。

int N;
int A[3030];
int cand[11];

map<pair<int,int>,int> M;

int ask(int a,int b) {
	
	if(a>b) swap(a,b);
	if(M.count({a,b})) return M[{a,b}];
	cout<<"? "<<a+1<<" "<<b+1<<endl;
	int x;
	cin>>x;
	return M[{a,b}]=x;
}
void ans() {
	int i;
	cout<<"!";
	FOR(i,N) cout<<" "<<A[i];
	cout<<endl;
	exit(0);
}

int detect(int v) {
	int i;
	int ret=0;
	FOR(i,11) if(v!=cand[i]) ret |= ask(v,cand[i])&(1<<i);
	return ret;
}



void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	MINUS(cand);
	while(1) {
		FOR(i,11) if(cand[i]==-1) break;
		if(i==11) break;
		while(1) {
			x=rand()%N;
			y=rand()%N;
			if(x!=y) break;
		}
		j=ask(x,y);
		FOR(i,11) if((j&(1<<i))==0) cand[i]=x;
	}
	int cmin=1<<12;
	int tar=-1;
	FOR(i,N) {
		if(tar==-1) {
			tar=i;
			cmin=detect(tar);
		}
		else if(ask(tar,i)==cmin) {
			x=detect(i);
			if(x<cmin) {
				cmin=x;
				tar=i;
			}
		}
	}
	FOR(i,N) {
		if(i==tar) A[i]=0;
		else A[i]=ask(i,tar);
	}
	cout<<"!";
	FOR(i,N) cout<<" "<<A[i];
	cout<<endl;
	
}

まとめ

シンプルな問題設定なのはいいね。