ABC212 C - Min Difference - かんプリンの学習記録

問題概要
解説
提出プログラム
感想

問題概要

長さ ${N}$ の数列 ${A}$ と長さ ${M}$ の数列 ${B}$ がある． ${\underset{1\leq i\leq N,1\leq j\leq M}{\min} |A_i-B_j|}$ を求めよ．

${1\leq N,M\leq 2×10^5\\ 1\leq A_i,B_i\leq 10^9}$

解説

愚直に実装すると ${O(NM)}$ になります．

各 ${i}$ 毎に ${|A_i-B_j|}$ が最小になるような ${j}$ を求めます．もちろんこのままだと ${i}$ 毎に ${O(M)}$ かかるのでダメですが ${A,B}$ をソートすることで以下の性質をもつようになります．

任意の ${i}$ に対して ${|A_{i}-B_{j}|}$ が最小になる ${j}$ を ${j_1}$ ， ${|A_{i+1}-B_{j}|}$ が最小になる ${j}$ を ${j_2}$ とすると ${j_1\leq j_2}$ が成り立つ．

これは ${|x-a|}$ が凸関数であることから簡単に分かります．
この性質が成り立つ場合に各 ${i}$ について最小値を取る ${j}$ を ${O(N+M\log{N})}$ で求められるアルゴリズムとしてMonotone Minimaというものがあります．それを用いると全体で ${O(N\log{N}+M\log{M})}$ で求められます．
上記の性質はMonotoneといいますが，もう少し条件を強めた性質「 ${B}$ の任意の部分集合についてもMonotoneである」が成り立つのでSMAWKアルゴリズムが使えます．これを用いると各 ${i}$ について最小値を取る ${j}$ を ${O(N+M)}$ で求められます．どちらにせよソートがネックになるので全体で ${O(N\log{N}+M\log{M})}$ かかります．