kmjp's blog

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

Codeforces #435 Div2 D. Mahmoud and Ehab and the binary string

まぁまぁの出来。
http://codeforces.com/contest/862/problem/D

問題

N文字のバイナリ列の一部を当てるinteractive問題である。
対象のバイナリ列は、0,1をそれぞれ最低1個含む。

クエリとして、N文字のバイナリ列を与えると正解とのハミング距離を返す。
このクエリを最大15回使い、0と1の場所を最低1箇所ずつ答えよ。

解法

まず1文字目だけを変えたクエリを2回行えば、先頭文字が0か1かわかる。
あとは残りの文字のどこかに先頭文字と逆のものがあるはずなので、それを求めよう。

例えば先頭文字が1なら、残りどこかに0があるはずである。
111111110000000のように1の範囲を伸ばしたり縮めたり二分探索すれば0が求まる。

int N;
int first,last;

string answer;

int ask(string s) {
	int ret;
	
	
	cout<<"? "<<s<<endl;
	/*
	int i,num=0;
	FOR(i,s.size()) num+=s[i]!=answer[i];
	return num;
	*/
	cin>>ret;
	return ret;
}

void ans(int a,int b) {
	cout<<"! "<<a<<" "<<b<<endl;
	exit(0);
}

int search1(int L,int R,int num0) {
	if(L+1==R) return L;
	int M=(L+R)/2;
	string q=string(N,'0');
	for(int i=L;i<M;i++) q[i]='1';
	int r=ask(q);
	if(r==num0+(M-L)) return search1(M,R,num0);
	return search1(L,M,num0);
}
int search0(int L,int R,int num0) {
	if(L+1==R) return L;
	int M=(L+R)/2;
	string q=string(N,'0');
	for(int i=L;i<M;i++) q[i]='1';
	int r=ask(q);
	if(r==num0-(M-L)) return search0(M,R,num0);
	return search0(L,M,num0);;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	/*
	cin>>answer;
	N=answer.size();
	*/
	cin>>N;
	x = ask(string(N,'1'));
	y = ask(string(1,'0')+string(N-1,'1'));
	
	first=(x<y);
	
	x=N-x;
	if(first==0) {
		ans(1,search1(1,N,x)+1);
	}
	else {
		ans(search0(1,N,x)+1,first);
	}
	
}

まとめ

interactive問題、面倒であまり好きになれないな…。