AtCoder-ABC212 C - Min Difference【Python解答例】
AtCoder Beginner Contest212のC問題についてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 212 - AtCoder
AtCoder Beginner Contest212 C - Min Difference
問題文
それぞれ N 個、M 個の正整数からなる 2 つの数列 A=(A1,A2,…,AN) と B=(B1,…,BM) が与えられます。
それぞれの数列から 1 つずつ要素を選んだときの 2 つの値の差の最小値、すなわち、 min1≤i≤N min1≤j≤M |Ai−Bj| を求めてください。
制約
・1≤N,M≤2×10^5
・1≤Ai≤10^9
・1≤Bi≤10^9
・入力は全て整数である。
解答例
import bisect n, m = map(int,input().split()) A = list(map(int, input().split())) B = list(map(int, input().split())) B.sort() ans = int(1e9) for i in range(n): point = bisect.bisect_left(B, A[i]) if point != 0: tmp = abs(A[i] - B[point-1]) else: tmp = abs(A[i] - B[point]) if point != len(B): tmp2 = abs(A[i] - B[point]) else: tmp2 = abs(A[i] - B[point-1]) ans = min(ans, tmp) ans = min(ans, tmp2) print(ans)
解説
ふたつの数列AとBから1つずつ要素を選んだとき、値の差の最小値を答える問題です。
Bをソートして、Aの各要素の挿入点を二分探索で求めました。
挿入点pointの前後の要素との差が最小値となり得るのでtmpおよびtmp2として計算しました。
この最小値をansとして更新することで求める答えとなりました。
ABC212の関連記事はこちら
ebisuke33.hatenablog.com