Codeforces #807 : Div2 F. Mark and the Online Exam

これまた本番のAC数に対し、upsolve数が多い問題。
https://codeforces.com/contest/1705/problem/F

問題

True/Falseで答える問題がN問ある。
N問の答えの組み合わせを提出すると、うち何問正解かが返るクエリがある。
最大N=1000のケースに対し、このクエリを675回まで使い、各問題の正解を求めよ。

解法

約2n/3回で解ける。
まずTTTT...とTFTF...のケースを求めておく。
次に、全体をTTT....にして2i-1問目と2i問目だけFにしたクエリを行うと、この２問の正答がTTかFFならこのクエリで確定できる。
そうでない場合、FTかTFの並びになるので、もう１問クエリを実行して確定させる必要があるが、ついでにもう１か所問い合わせを出して2回の問い合わせで３問確定させよう。

int N;
vector<int> V;
int ret[1010];
int ask(vector<int> V) {
	FORR(v,V) cout<<"FT"[v];
	cout<<endl;
	int ret;
	cin>>ret;
	if(ret==N) exit(0);
	return ret;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	vector<int> X,Y;
	FOR(i,N) {
		X.push_back(1);
		Y.push_back((i+1)%2);
	}
	int tx=ask(X);
	int ty=ask(Y);
	vector<int> unfixed;
	FOR(i,N) if(i>=N/3*2) unfixed.push_back(i);
	
	FOR(i,N/3) {
		vector<int> X2=X;
		X2[2*i]=X2[2*i+1]=0;
		k=ask(X2);
		if(k>tx) {
			ret[2*i]=ret[2*i+1]=0;
		}
		else if(k<tx) {
			ret[2*i]=ret[2*i+1]=1;
		}
		else {
			vector<int> Y2=Y;
			r=-1;
			if(unfixed.size()) {
				r=unfixed.back();
				unfixed.pop_back();
			}
			Y2[2*i]=0;
			Y2[2*i+1]=1;
			if(r!=-1) {
				Y2[r]=Y[r]^1;
				k=ask(Y2)-ty;
				if(k==3) {
					ret[2*i]=Y2[2*i];
					ret[2*i+1]=Y2[2*i+1];
					ret[r]=Y2[r];
				}
				if(k==1) {
					ret[2*i]=Y2[2*i];
					ret[2*i+1]=Y2[2*i+1];
					ret[r]=Y2[r]^1;
				}
				if(k==-1) {
					ret[2*i]=Y2[2*i]^1;
					ret[2*i+1]=Y2[2*i+1]^1;
					ret[r]=Y2[r];
				}
				if(k==-3) {
					ret[2*i]=Y2[2*i]^1;
					ret[2*i+1]=Y2[2*i+1]^1;
					ret[r]=Y2[r]^1;
				}
			}
			else {
				k=ask(Y2);
				if(k>ty) {
					ret[2*i]=Y2[2*i];
					ret[2*i+1]=Y2[2*i+1];
				}
				else {
					ret[2*i]=Y2[2*i]^1;
					ret[2*i+1]=Y2[2*i+1]^1;
				}
			}
		}
	}
	FORR(r,unfixed) {
		vector<int> X2=X;
		X2[r]=0;
		k=ask(X2);
		if(k<tx) ret[r]=1;
	}
	
	FOR(i,N) X[i]=ret[i];
	ask(X);
	//assert(0);
	
	
}

まとめ

Editorialを見てしまえば納得できるけど、これを本番中に自力で出すの結構しんどいな。