yukicoder : No.1793 実数当てゲーム

こういう問題、yukicoder以外では出しにくそう。
https://yukicoder.me/problems/no/1793

問題

1.22×10^74以下のある実数Xを当てるゲームである。
実数Yを指定し、YがX以下がどうかを答えてもらうクエリを最大24回まで行うことができる。
絶対誤差または相対誤差が10^-5以下ならACとなる。

解法

ε=10^-5とする。
真の解がZであるとき、(1-ε)Z以上(1+ε)Z以下を答えると解になる。
そこで、解の候補を以下のように列挙する。

• 1以下の候補は、2ε区切り
• 1以上の候補は、(1+2ε)^kの形のもの

(1+2ε)^kをk=2^24まで取ると、10^74は余裕で超える。そこで下記の解では念のためε=7.5×10^-6と少し小さくしている。

解の候補は2^24以下なので、24回以下のクエリで
(1+2ε)^k≦X＜(1+2ε)^(k+1)
となるkを求められる。あとはこの区間全体が誤差の範囲に含まれるよう、(1+2ε)^kと(1+2ε)^(k+1)の平均を答えよう。

int T;
double R=0; //3.14159565351e59;

int ask(double D) {
	cout<<fixed<<setprecision(100)<<"? "<<D<<endl;
	string s;
	cin>>s;
	return s=="Yes";
	
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	vector<double> V;
	FOR(i,100000) V.push_back(i*0.00001);
	for(i=0;V.size()<=(1<<24);i++) V.push_back(min(12.22e74,pow(1.000015,i)));
	cin>>T;
	while(T--) {
		int L=0;
		for(i=23;i>=0;i--) if(ask(V[L+(1<<i)])) L+=1<<i;
		cout<<fixed<<setprecision(100)<<"! "<<((V[L]+V[L+1])/2.0)<<endl;
	}
}

まとめ

最初(1+ε)^(2^24)が10^72位にしかならないなーと悩んでいた。
一方(1+2ε)^(2^24)だと10^74を余裕で超えてしまうので、なぜXの上限が1.22*10^74なのかよくわからなかった。