詰まって自力で解けなかったのでメモ。
問題概要
$N$ 個の箱があり、箱 $i$ は座標 $i$ に置かれており、そのうち $K$ 個が光っている。
以下の質問を $60$ 回以下することで、光っている箱を ( $K$ 個のうち) $2$ つ当てよ。
$a$ $b$ : 「箱 $a$ から最寄りの光っている箱までの距離」が「箱 $b$ から最寄りの光っている箱までの距離」以下であれば Yes そうでないなら No
$2 \le K \le N \le 10^5$
「光っている箱が $2$ つ以上ある」というのが実は枷。とりあえず「光っている箱を $1$ つ当てる」という方針を取る。
鍵となるのは「 $[l,r]$ に少なくとも $1$ つある」という情報を持ち続けること。最初は「 $[1,N]$ に少なくとも $1$ つある」から始めます。
$mid$ を区間の真ん中として、 $mid,mid+1$ を訊きます。すると、以下が言えます。
- 返答が Yes なら $[l,mid]$ に少なくともひとつある
- 返答が No なら $[mid+1,r]$ に少なくともひとつある
ここで重要なのは、 $mid$ をうまく定めることで $ l - 1 $ に箱があったり、 $r+1$ に箱があったりという場合でもこわれないようにすることが出来るということです。この理由は、区間内の任意の箱への距離が区間外の任意の箱への距離以下であることにあります。
こうして、光る箱 $x$ を見つけられました。では、 $2$ つ目の箱を見つけていきましょう。
次に解きたい問題は、 $[1,x-1],[x+1,N]$ のどちらに光る箱が少なくともひとつあるかというものです。
ここまでくるとこれを解くことはそう難しくなく、以下を繰り返していけばよいです。
- 左側の区間の真ん中を $mid$ として $mid$ と $mid+1$ を訊く。
こうして光る箱がある区間がどちらかわかれば、あとは最初に箱を $1$ つ特定した時と同じことをすればよいです。
なお、「区間の真ん中」と言葉を濁しましたが小数点以下の処理を間違うと壊れるので、丁寧に詰める必要があります。このへんは実装を参照。
