kmjp's blog

競技プログラミング参加記です

Codeforces #427 Div2 E. The penguin's game

結果はグダグダだったけど勉強にはなった。
http://codeforces.com/contest/835/problem/E

問題

N要素の数列がある。
うち2つはYで残りはすべてXである。

以下のクエリを最大19回用い、数列中でYの要素を当てよ。

  • 要素の集合を指定すると、それらのxorの値が返る。

解法

クエリによって返る値は0,X,Y,X^Yのいずれかであり、これらは互いに異なる。
よって返り値がYかX^Yであれば、指定した要素の中に1つだけYがあり、そうでなければ0個か2個Yがある。

仮に要素がYとなるindexがAとBだとする。
クエリに1~Nの要素中でd bit目が1のものをすべて指定すれば、A,Bのd bit目における1の個数がわかる。
言い換えればA^Bのd bit目の値がわかる。

よってまずd=0~9に対しこの調子でA^Bを求めよう。
A!=Bなので、少なくとも1つのbitでは1の個数が1個となる。
仮にe bit目がそうであったとする。

以後のクエリでe bit目が0の要素だけを対象とすれば、Bの影響がクエリに現れることはない。
よって、再度d=0~9に対しクエリを行う。ただしd=eの時はクエリを実行せず、また他のクエリの時もe bit目が0のものだけを対象とする。
これによりAが判明するので、A^BよりBも判明する。

前半で10回、後半で9回クエリを実行するので19回でA,Bを特定できる。

int N,X,Y;
int R1,R2;
//#define DEB

int ask(vector<int> V) {
	cout<<"? ";
	cout<<V.size();
	FORR(c,V) cout<<" "<<c+1;
	cout<<endl;
	fflush(stdout);
	int ret=0;
#ifdef DEB
	FORR(c,V) {
		if(c+1==R1 || c+1==R2) ret^=Y;
		else ret^=X;
	}
#else
	cin>>ret;
#endif
	return ret;
}

int answer(int a,int b) {
	cout<<"! "<<a+1<<" "<<b+1<<endl;
	//exit(0);
}

bitset<1024> cand[10][2];
int ret[10][2];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>X>>Y;
#ifdef DEB
	cin>>R1>>R2;
#endif
	
	int diff=0,high=0;
	FOR(i,10) {
		vector<int> A;
		FOR(x,N) if(x&(1<<i)) A.push_back(x);
		if(A.empty()) continue;
		x = ask(A);
		if(x==(X^Y) || x==Y) diff |= 1<<i, high=i;
	}
	
	int dif2=0;
	FOR(i,10) if(i!=high) {
		vector<int> A;
		FOR(x,N) if((x&(1<<i))&&((x&(1<<high))==0)) A.push_back(x);
		if(A.empty()) continue;
		x = ask(A);
		if(x==(X^Y) || x==Y) dif2 |= 1<<i;
	}
	
	answer(dif2,diff^dif2);
	
}

まとめ

以前も2個の要素を当てるinteractiveをやったことがあったけど、これは思い浮かばなかった。