問題

https://atcoder.jp/contests/abc364/tasks/abc364_d

要点

• $k$ 番目を求めるときは二分探索を頭にいれる。
• ある座標からの距離など負の値が混じる場合は二分探索がしにくいが、しやすい形に変形できないか考える。
• この場合だと個数を二分探索することによって解きやすい形に変形した。

事前情報として二分探索で解ける問題ということを知っていた。

数直線の座標はとりあえずソート

そして $b$ から見て $k$ 番目の座標をどうやって探すかを考える。

• 全探索 → 論外
• $A$ の全ての要素に対して $inf$ を足せば楽に二分探索出来そう。→ 反例がたくさんある それをするなら $b$ に対しても $inf$ を足さなければいけない。意味を為す操作になりえない。

$b$ の地点から正の方向に二分探索、負の方向に二分探索すればうまく出来そうだと考えた。

正の方向に $k$ 番目のものを探しても負の方向にも $k$ 番目のものがあるかもしれない → これをやるくらいなら全探索したほうがいいし、おそらく指数時間かかる。

解説を見たあと話

$b$ から見て絶対値の範囲距離 $x$ の中に点がちょうど $k$ 個あればそれが答えになる。(もちろん $x$ は $k$ 個ある範囲のうちの最小!)

$x$ が取りうる範囲を考えて二分探索 → $b-x$ から $b+x$ の範囲内に点がいくつあるか高速に求められれば答えを求めたも当然である。