【競プロ典型90問】007の解説（python）

概要

競プロ典型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を押していただけると嬉しいです。
（記事投稿のモチベになります。）

ここまでお読みいただきありがとうございました。