AtCoder ARC #078 : E - Awkward Response

なんとか赤く戻った。
http://arc078.contest.atcoder.jp/tasks/arc078_c

問題

下記クエリを最大64回行い、[1,10^9]の範囲に含まれる整数Nを当てるインタラクティブ問題である。

クエリでは[1,10^18]の整数nを指定すると、以下のいずれかを満たす場合真が返る。

• n≦Nかつ10進数文字列表記でもn≦N
• n＞Nかつ10進数文字列表記でもn＞N

解法

まず桁数を特定しよう。
Nが10の累乗ではない場合、nに10の累乗を投げると文字列表記でn≦Nを満たすので、クエリの結果は結局数値でn≦Nかどうかを返す。
よって1～10^10まで順に10の累乗をクエリで投げ、桁数を特定する。

Nが10の累乗の場合、n=10^10でも真が返ってしまう。
この場合、逆に9,99,999...と比較することで文字列表記でn＞Nを満たすので、クエリの結果は結局n＞Nかどうかを返すものとなり、同様に桁数を特定できる。

Nが10の累乗でない場合を考える。
nに10^9を超える数字を指定すれば、数値でn＞Nは確実なのでクエリは文字列表現でn＞Nかどうかを返す。
これを利用して上位の桁から値を特定して行く。
二分探索すれば1桁4回のクエリで特定できる。

int ask(ll v) {
	string S;
	cout<<"? "<<v<<endl;
	cin>>S;
	return S[0]=='Y';
}

void ans(ll v) {
	cout<<"! "<<v<<endl;
	exit(0);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	ll p10=10000000000LL;
	for(i=10;i>=1;i--) {
		if(ask(p10)==1) break;
		p10/=10;
	}
	
	if(i==10) {
		p10=10000000000LL;;
		for(i=10;i>=1;i--) {
			if(ask(p10-1)==0) ans(p10);
			p10/=10;
		}
	}
	if(i==0) {
		for(i=10;i<=90;i+=10) {
			if(ask(i)==1) ans(i/10);
		}
	}
	ll ret=0,cm=0;
	for(;p10>=1;p10/=10) {
		int cur=-1;
		int dd[4]={8,4,2,1};
		FOR(j,4) if(cur+dd[j]<10) {
			ll tmp=ret+(cur+dd[j])*p10;
			ll tmp2=cm*10+(cur+dd[j]);
			if(ask(tmp2*1000000000LL)==0) cur+=dd[j];
		}
		cm=cm*10+cur;
		ret+=p10*cur;
	}
	
	
	ans(ret+1);
	
}

まとめ

1発AC出るとは思ってなかった。