ABC466 C - Count Close Pairs

考え方

まず、問題で言及されていないが、座標は当然整数とは限らないことに注意したい。

さて、インタラクティブ問題ということで身構えそうになるが、実はそこまで特殊なことはない。
普通に長さ $N$ の数列を渡されたと思って、そこから同様の問題を解くにはどうするか。
どうせ vector の中身は「これとこれの差 $1$ 以下？」しか見ない。
その確認が、vector の生データの引き算を if 文にかけるか、ジャッジに訊くかが変わっただけである。

とはいえ、今回の問題ではもう $1$ つ影響する点がある。
普通に長さ $N$ の数列を渡された場合、vector の中身の確認は、計算量が許す限り好きなだけ行える。
しかし、今回は $2N$ 回に制限されている。
確認がそれ以内に収まらなければならず、$O(N \log N)$ 回問い合わせて二分探索で解く方法は使えない。

ということで、これが $O(N)$ で済む尺取法を用いればよい。
vector の中身を $1$ 回確認するたびに $2$ つのインデックスの片方が必ず $1$ 進む。
つまり、両方のインデックスが最大 $N$ 回ずつ進む間の確認回数は $2N$ 回以下である。

インタラクティブ問題は、動作テストが難しい。
一度、普通の vector でテストをしながら尺取法を書き、最後に問い合わせ部分を書き換えるとよい。

具体例での動作

$N=5$ で、点 $1$ から点 $5$ までの座標が次のようになっている場合を考える。
これらの座標自体は、プログラムには入力されない。

点1: 0
点2: 0.4
点3: 0.8
点4: 1.5
点5: 3

最初は左端を点 $1$ とする。
右端を点 $1$ から順に動かすと、次のようになる。

右端が点 $5$ のときは、左端も点 $5$ まで進む。
同じ点同士については問い合わせず、条件を満たすものとして扱う。

実際に行った問い合わせは $7$ 回であり、上限の $2N=10$ 回以下である。
したがって、最後に ! 4 と出力する。

注意点

うっかり、"? 3 3" のような質問を投げないこと。
これは不正な質問である。
尺取法でこのような質問が生まれる場面は存在するので、問い合わせを投げずに "Yes" と判断する。

問い合わせを出力するたびに、標準出力を flush する必要がある。
出力後の改行に endl を用いることで改行ついでに flush される。

別解

特になし。