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

最初は、l=1、result=0 である。

r=1 のとき、l=r なので、実際には問い合わせずに true として扱う。
r-l=0 を result に加える。

l: 1
r: 1
result: 0

r=2 のとき、? 1 2 と問い合わせる。
点 $1$ と点 $2$ の距離は $0.4$ なので、返答は Yes である。
r-l=1 を result に加える。

l: 1
r: 2
result: 1

r=3 のとき、? 1 3 と問い合わせる。
点 $1$ と点 $3$ の距離は $0.8$ なので、返答は Yes である。
r-l=2 を result に加える。

l: 1
r: 3
result: 3

r=4 のとき、まず ? 1 4 と問い合わせる。
点 $1$ と点 $4$ の距離は $1.5$ なので、返答は No である。
そこで、l を $1$ 増やす。

次に、? 2 4 と問い合わせる。
点 $2$ と点 $4$ の距離は $1.1$ なので、返答は No である。
再び、l を $1$ 増やす。

次に、? 3 4 と問い合わせる。
点 $3$ と点 $4$ の距離は $0.7$ なので、返答は Yes である。
r-l=1 を result に加える。

l: 3
r: 4
result: 4

r=5 のとき、まず ? 3 5 と問い合わせる。
点 $3$ と点 $5$ の距離は $2.2$ なので、返答は No である。
そこで、l を $1$ 増やす。

次に、? 4 5 と問い合わせる。
点 $4$ と点 $5$ の距離は $1.5$ なので、返答は No である。
再び、l を $1$ 増やす。

l=r=5 になったので、実際には問い合わせずに true として扱う。
r-l=0 を result に加える。

l: 5
r: 5
result: 4

最後に、! 4 と出力すればよい。

実際に行った問い合わせは $7$ 回であり、上限の $2N=10$ 回以下である。

注意点

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

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

別解

特になし。