結果はグダグダだったけど勉強にはなった。
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をやったことがあったけど、これは思い浮かばなかった。