AtCoder Regular Contest 078 E - Awkward Response

http://arc078.contest.atcoder.jp/tasks/arc078_c

問題概要

ある正整数Nが設定されている。64回以内の質問クエリでNを特定せよ。質問クエリで正整数nを投げると、「n <= N かつ str(n) <= str(N)」または「n > N かつ str(n) > str(N)」 のときYESが、そうでないときNOが返ってくる。

1 <= N <= 10⁹

1 <= n <= 10¹⁸

解法

桁数を特定してから2分探索する。

まず桁数の特定は10, 100, 1000, ... を順に投げていくとできる。例えばN=152のとき100まではYESだが1000以降はNOが返る。一般的には初めてNOになるときのnを10^xとすると、Nは 10^x-1 < n < 10^x ということがいえる。（ただしNが10^xの形をしているときがコーナーケースで、この場合はいつまでもNOが返ってこない。この場合は次に2, 20, 200, ... という風に投げていけばNを特定できる）

桁数が特定できたらあとは二分探索を行う。ここで推測する数字をそのまま質問してもダメ（例えばN=123のとき、122も123も124も返答はYESになってしまう）で、工夫が必要になる。自分はnに10⁹を掛けることにした。Nの桁は決まっているので、同じ桁のnに対して10^xを掛ければ数字での比較は必ずn > Nになる。一方で文字列での比較は10^xを掛ける前と変わらないので、Nを境に大小が切り替わる。これで2分探索ができる。

前半で高々9回、後半でだいたいlog_2(10⁹) ≒ 30回の質問クエリになり、制約内に収まる。

感想

整理すると結構すっきりするけど最初もっとぐちゃぐちゃなやり方でやってしまった。D言語のdebug構文をうまく使えた感じがある

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;
 
long N, cnt;
 
bool ask(long n) {
    writeln("? ", n);
    stdout.flush;
    cnt += 1;
    
    debug {
        string sn = n.to!string;
        string sN = N.to!string;
        return (n <= N && sn <= sN) || (n > N && sn > sN);
    } else {
        return readln.chomp == "Y";
    }
}
 
void main() {
    debug {N = readln.chomp.to!long;}
 
    long x = 10;
    for (; x <= 10^^9 && ask(x); x *= 10) {}
 
    if (x == 10L^^10) { // N = 1, 10, 100, ...
        x = 2;
        for (; x <= 2 * 10L^^9 && !ask(x); x *= 10) {}
        writeln("! ", x / 2);
    } else {
        long hi = x - 1;
        long lo = x / 10;
        while (hi - lo > 1) {
            long mid = (hi + lo) / 2;
            if (ask(mid * 10L^^9)) hi = mid;
            else lo = mid;
        }
        writeln("! ", hi);
    }
 
    debug {cnt.writeln;}
}