日刊競プロ ABC 212 -C - Min Difference-

C - Min Difference

問題文
それぞれ N 個、M 個の正整数からなる 2 つの数列 A=(A1,A2,…,AN) と B=(B1,…,BM) が与えられます。それぞれの数列から 1 つずつ要素を選んだときの 2 つの値の差の最小値、すなわち、
Σ1≤i≤Nmin 1≤j≤M min ∣Ai−Bj∣ を求めてください。

制約
1≤N,M≤2×10**5
1≤Ai≤10**9
1≤Bi≤10**9
入力は全て整数である。

考えたこと

素直にNとMの組み合わせを全探索するとTLEになる．（経験談）

どうにか探索数を減らすことができないかを考える．差の絶対値を求める問題なので，AiとBjと組み合わせのうち一番近いものは何か？という問題として考えられる．
そこでAiを数列Bjの中に入れたときに小さくなるものはどこか？という風に考える．

あとはAの数だけ，2分探索でBの中で最適な場所を探せば良い．
計算数はN×logMとなる．

import bisect
N,M = map(int,input().split())
Alist = list(set(list(map(int,input().split()))))
Blist = list(set(list(map(int,input().split()))))
Alist.sort()
Blist.sort()
mini = float('INF')
for i in range(len(Alist)):
 #bisectで挿入点の右側を出力する
 tmppoint = bisect.bisect(Blist,Alist[i])
 #Alist[i]がBlistの中で一番小さい場合
 if tmppoint==0:
   tmp1 = abs(Alist[i]-Blist[tmppoint])
 else:
   tmp1 = abs(Alist[i]-Blist[tmppoint-1])
 #Alist[i]がBlistの中で一番大きい場合
 if tmppoint==len(Blist):
   tmp2 = abs(Alist[i]-Blist[tmppoint-1])
 else:
   tmp2 = abs(Alist[i]-Blist[tmppoint])
 mini = min(mini,tmp1)
 mini = min(mini,tmp2)
print (mini)

​

2分探索を使うので，BをSortする必要がある．（自分は被りとかも嫌だったのでset関数とかも使ってますが．．．）

追記

サムネはオフィスからの写真です（内容と全く関係ないです）