Google Code Jam 2020 Qualification Round : D. ESAb ATAd

意地でも二分探索にさせたくないのかな…。
https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd27/0000000000209a9e

問題

N文字のバイナリ列Bを当てるInteractive問題である。
1回のクエリで、1か所の文字を指定してその0/1を得ることができる。
ただし10回行うごとに、0/1反転と左右反転それぞれ50%の割合で生じる。(両方生じることもある)。
150回以内のクエリで、バイナリ列の状態を求めよ。

解法

10回枚にバイナリ列が変化する可能性があるので、そのつど2手使って何が起きたかを求めていこう。
そうすると残り8手で8つずつ値を確定できる。

まず2手で未確定のB[i],B[N-1-i]を求める。
もし値が一致するなら、ここは以後0/1反転の有無の確認に使えるので、その場所を覚えておく。
一致しないなら0/1反転か左右反転のどちらかがあったことの確認に使えるのでその場所を覚えておく。
もし途中後者のみ登場して前者が登場しないと、値が変化しても0/1反転と左右反転のどちらの要因によるものか判定できないが、いずれでも変化の仕方は同じなのでそこは構わない。

int T,B;
int A[101];
int ask(int pos) {
	int x;
	cout<<pos+1<<endl;
	cin>>x;
	//cerr<<pos<<" "<<x<<endl;
	return x;
}

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	int flipped=-1;
	int rev=-1;
	int cur=0;
	FOR(i,15) {
		int num=10;
		//cerr<<"!"<<i<<cur<<endl;
		if(flipped>=0) {
			x=ask(flipped);
			num--;
			//cerr<<"flipp"<<endl;
			if(A[flipped]!=x) {
				FOR(j,B) A[j]^=1;
			}
		}
		if(rev>=0) {
			x=ask(rev);
			num--;
			//cerr<<"rev"<<endl;
			if(A[rev]!=x) {
				FOR(j,B/2) swap(A[j],A[B-1-j]);
			}
		}
		while(cur<B/2 && num>=2) {
			num-=2;
			A[cur]=x=ask(cur);
			A[B-1-cur]=y=ask(B-1-cur);
			if(x==y) flipped=cur;
			else rev=cur;
			cur++;
		}
		if(cur==B/2&&num) {
			FOR(i,B) cout<<A[i];
			cout<<endl;
			string s;
			cin>>s;
			//cerr<<s<<endl;
			assert(s=="Y");
			return;
		}
		if(num) ask(0);
	}
}

void init() {
	cin>>T>>B;
}

まとめ

GCJのInteractive苦手。