概要
競プロ典型90問の解説記事です。
解説の画像を見ても分からない（理解力が足りない）ことが多々あったので、後で解き直した際に確認できるようまとめました。
※順次、全ての問題の解説記事を挙げていく予定です。
※★５以上の問題は難易度的に後回しにしているため、投稿時期が遅くなる可能性があります。（代わりに丁寧に解説してくれる方いたらぜひお願いします）
問題007-CP Classes
問題概要
配列Aの中から、各Bに最も近い値を見つけ、その絶対値を出力する。
解き方
まず初めに、全てのA、Bの組み合わせにおいて、順番に絶対値を求めていく方法が考えられるかと思います。
しかし、この考えでは、計算量がNQとなり、N, Qはそれぞれ$10^5$オーダーのため、TLEとなります。
そこで今回は、事前にAをソートし、二分探索を行うことで、Bに最も近い値を高速で求めます。
この時の計算量は、ソートの際にかかる計算量が$NlogN$、Bに近い値の二分探索に$logN$、その計算をQ回行うので、合計の計算量は$(N+Q)logN$となり、これは時間内に十分に間に合います。
※二分探索に関しては、こちらをご参考ください。
実装の流れは以下になります。
1. Aをソートする。
2. Bに近い値を二分探索で求め、絶対値を計算、出力する。
引用元：競プロ典型90問 Github
実装
answer.py
# 入力の受け取り
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
# Aをソート
A.sort()
# 出力する答えを配列で格納
ans = []
for i in range(Q):
b = int(input())
# b以下を満たす範囲をleft, bより大きい範囲をrightとする
left = -1
right = N
while right - left > 1:
mid = (right + left)//2
if A[mid] <= b:
left = mid
else:
right = mid
# B以下を満たす値とBより大きい値で、絶対値を比較する。
# leftの境界値を含まないようifで条件分岐
comp1 = 10**9
comp2 = 10**9
if left >= 0:
comp1 = abs(A[left]-b)
if left < N-1:
comp2 = abs(A[left+1]-b)
ans.append(min(comp1, comp2))
# 答えを出力
for i in range(Q):
print(ans[i])
最後に
問題の解説を読んでも他の人のコードを見てもさっぱり分からないという方の
力に少しでもなれれば幸いです。
コードの改善点やその他、ご意見などあれば、気軽にコメントください。
また、この記事を読んで理解できた方はぜひLGTMを押していただけると嬉しいです。
（記事投稿のモチベになります。）
ここまでお読みいただきありがとうございました。