https://prd-xxx.hateblo.jp/entry/2024/07/30/000457

先日こんな問題が出ました ABC364-D K-th Nearest

(概要)

数直線上に $N$ 個の点があるので、以下のクエリに $Q$ 個答えてください。

$N$ 個の点のうち座標 $x$ から $K$ 番目に近い点との距離を求めよ

$N$ も $Q$ も ${10}^5$ ありうるので、愚直に調べるのはTLEします。

じつは

$K$ 番目に近い点の距離を求めよ

という問題はにぶたん (二分探索) が相性が良いです。

にぶたんで解ける問題にするために、問題の言い換えが必要なのですが、
これは筆者がとても苦手としていて毎回10分ぐらい悩むので、次に出てきたら使えるようにメモしておきます。
以下が結論です。　

$x$ から $K$ 番目に近い点の距離を求めよ

↓(言い換え)

「 $x$ から距離 $d$ 以下の点が何個ある？」の答えが $K$ 個以上になる最小の $d$ はいくつ？

です。
どういうこと？ほんとにそうなの？は後述するとして、この言い換えができれば
「距離 $d$ 以下の点が何個ある？」の問いに高速に答えられれば、にぶたんが使える！となります。

実際、この問題では $x$ の左右両側を調べる必要がある点に注意ですが、
$x$ と $d$ が決まっていれば
bisect_right(A, x+d) - bisect_left(A, x-d) 等のようにすれば「 $x$ から距離 $d$ 以下の点の個数」が求まります
これを使ってにぶたんをすると問題をACできます (にぶたん in にぶたん ¹)

どういうこと？ほんとにそうなの？

左右を見る問題はちょっと複雑なので単純にします。

距離に限らず、比較可能な数値であれば適用できます。
ソートされた数列があり、これの「小さい方から $K$ 番目」を求めることにします。²

$A = [1,2,2,3,4,4,5,6$ ]

これの、
「小さい方から $K$ 番目」の値
と、
「 $a$ 以下の値は何個？」の答えが $K$ 個以上になる最小の $a$ はいくつ？
の答えが一致することを確認します。

まず、 $a$ 以下の値は何個？を小さい方から調べてしまいます。　

$0$ 以下の値は？: $0$ 個
$1$ 以下の値は？: $1$ 個
$2$ 以下の値は？: $3$ 個
$3$ 以下の値は？: $4$ 個
$4$ 以下の値は？: $6$ 個
$5$ 以下の値は？: $7$ 個
$6$ 以下の値は？: $8$ 個

のようになっています。　
例えば $K=4$ のときを見ていきます。　
$a$ が小さい方から見ていって、 $a$ 以下の値は？が初めて $4$ 個以上になるのは、確かに $a=3$ の時で、 $A$ の $4$ 番目の値は $3$ です。　
また、 $K=5$ のとき、　
$a$ 以下の値は？が初めて $5$ 個以上になるのは、 $a=4$ の時で、 $A$ の $5$ 番目の値は $4$ です。　
同様に、 $K=6$ のとき、
$a$ 以下の値は？が初めて $6$ 個以上になるのは、 $a=4$ の時で、 $A$ の $6$ 番目の値は $4$ です。　

他の場合を試しても、確かに言い換えが正しいことがわかります。³　

(おまけ) 言い換えのバリエーション

「スコアが小さい方から $K$ 番目の人」を求めよ

↓ (言い換え)

①「スコア $a$ 以下の人は何人？」の答えが $K$ 人以上になる最小の $a$ はいくつ？
②「スコア $a$ より大の人は何人？」の答えが $(N-K)$ 人を超えない最大の $a$ はいくつ？
③「スコア $a$ 以上の人は何人？」の答えが $(N-K+1)$ 人以上になる最大の $a$ はいくつ？
④「スコア $a$ 未満の人は何人？」の答えが $(K-1)$ 人を超えない最小の $a$ はいくつ？

「スコアが大きい方から $K$ 番目」「大きい方から $K$ 位」の場合は以下の通りです。

↓ (言い換え)

⑤「スコア $a$ 以上の人は何人？」の答えが $K$ 人以上になる最大の $a$ はいくつ？
⑥「スコア $a$ 未満の人は何人？」の答えが $(N-K)$ 人を超えない最小の $a$ はいくつ？
⑦「スコア $a$ 以下の人は何人？」の答えが $(N-K+1)$ 人以上になる最小の $a$ はいくつ？
⑧「スコア $a$ より大の人は何人？」の答えが $(K-1)$ 人を超えない最大の $a$ はいくつ？

頑張ってバリエーションを考えてみたものの、とりあえず①と⑤があれば良さそうですかね。^^

おわり

にぶたんマスターになろう！

界隈では「log2つ」とかよく言われますね　NやlogNの大きさなどにもかなりよりますが、2つまでならPyPyでギリギリ通るようになってることが多いです↩
「小さい方からK番目」「小さい方からK位」ときたらこのパターンを引き出せるようにしたいですね↩
もっと論理的な説明ができればかっこよかったんですが「実例を確認する」にしてお茶を濁したゴリラです...↩