AtCoder Beginner Contest 212 [ C - Min Difference ]をPythonで解く（300点、⬜️灰色diff）

問題

atcoder.jp

解法

数列A、数列Bが2 x 10⁵なので、A,Bの全要素に対して総当たりだと、2 x 10⁵の2乗なので10⁸越えでTLE確実。

なにか最適化する必要がある。
おそらく二分探索だろうと、検索したところ、そういえばbisectという便利ライブラリがPythonにはあることを思い出す。

数列A、Bをソート。
数列Aの各要素に近い値を数列Bからbisect_rightで二分探索。
bisect_rightの結果のIはB[I-1]とB[I]を使用。
計算量はO(N logM)。

実装