ARC078 E : Awkward Response

atcoder.jp

解法

二分探索を考えると、問題になるのは判定したい数より大きいのか小さいのかです。
2クエリで1回の探索を以下の方法で実現できます。

判定したい数を$ n $とする。

①$ n $をクエリに投げる
②$10n$をクエリに投げる
③①と②で"Yes"と"No"が入れ替われば$ N > n $。そうでなければ$ N \leqq n $。

よって$ 2log_2 N $回で解を求めることができ、64回に収まります。

10倍しても(右端に0を1つつけても)辞書順はほとんど変わらず、数の大きさだけを変えることができるので、$ n $より大きい場合のみに対して結果を変えることで判定を行うことができます。

具体例を以下に示します。ここでは$ n = 28$とします。

①$ N = 52 $
このとき、最初のクエリでは$28 < 52$かつ$str(28) < str(52)$のため"Yes"が返りますが、10倍の280で判定を行うと$280 > 52$かつ$str(280) < str(52)$となるため、確かに結果が入れ替わっています。これは最初に"No"が返ってきたときも同様です。

②$ N = 9 $
このとき、最初のクエリでは$9 < 28$かつ$str(9) > str(28)$のため"No"が返ります。10倍の280で判定を行っても同じように$9 < 280$かつ$str(9) > str(280)$なので"No"が返ります。

int main(){
    ll l = 0, r = 1000000000;
    while(r-l > 1){
        ll m = (l+r) / 2;
        cout << "? " << m << endl;
        char c; cin >> c;
        ll M = m * 10;
        cout << "? " << M << endl;
        char d; cin >> d;
        if(c != d) l = m;
        else r = m;
    }
    cout << "! " << l + 1 << endl;
}