ebisukeプログラミング初心者脱出黙示録

30歳を過ぎてから始めたプログラミングと競プロの記録。Pythonで取り組んでいます。Arduinoで電子工作も

AtCoder-ABC212 C - Min Difference【Python解答例】

f:id:ebisuke33:20210731225513p:plain

AtCoder Beginner Contest212のC問題についてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 212 - AtCoder



AtCoder Beginner Contest212 C - Min Difference

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