Atcoder典型90問 007 - CP Classes

Atcoder典型90問 007 - CP Classes（★3）

▶︎https://atcoder.jp/contests/typical90/tasks/typical90_g

問題

ABC 競技プログラミング塾には N 個のクラスがあり、
番号 i (1≤i≤N) のクラスはレーティング Aiの生徒を対象としています。

今、Q 人の生徒がこの塾に入塾しようとしています。 番号 j (1≤j≤Q) の生徒のレーティングは Bjです。 各生徒は自分に合わないレベルのクラスに行くと不満になります。 各生徒について、その不満度は次のように定義されます。

対象レーティング a と自分のレーティング b の差の絶対値、すなわち
∣a−b∣
j=1,2,3,…,Q それぞれについて、番号 j の生徒の不満度として考えられる最小値を求めてください。 ただし、1 人も入らないクラス、複数人から成るクラスがあっても良いものとします。

制約

1≤N≤300000 \\
1≤Q≤300000 \\
0≤A_i≤10^9 \\
0≤B_j≤10^9\\
 
入力はすべて整数

試したこと

• 見るからに二分探索。O(QlogN)なのでPypyならギリ通るかなという感じ。→Pythonでも通った、えらい。
• 「最も近い」というのが上側か下側かわからないので、二分探索で区間の両端を絞ってから近さを判定しようかなという感じ
• とけた

適切な方針 & 二分探索の説明

• 上でOKそうなので計算にかかった時間のみ記載しておく。いずれもAC
• Pypy3 : 1201 ms
• Python 3.8.2 : 2259 ms]
• 二分探索 :
  • ソートされた配列に対して、目標値を含むような区間を特定する操作。
  • left以上right以下が探索区間で、この区間を目標値を含むように狭めていく=leftとrightを近づける方向に更新していく。
  • 辞書を引くイメージ。たとえば「ねこ」を引きたい時に、leftを「あ」、rightを「ンジャメナ」にすると、ねこは必ずleft以上right以下の区間に含まれている。このときに配列の中央値midを調べて、midが「はまち」だったら、ねこはmidからみてleft側にあるはずなので、midを新しいrightに設定すれば、目標値を含むようなより狭い区間が得られる。
  • これを繰り返すと、結果として半分ずつに区間を分割していき、目標値が存在するエリアを絞り込むことができる。
  • 例) left ~~ (ねこ) ~~ mid ~~ right　という位置関係になった場合は
    left ~~ (ねこ) ~~ mid = 新しいright ~~ 古いright
    とすると区間幅を1/2倍にできる。
  • これを繰り返すといずれ区間幅が1となり、「ねこ」の位置が特定される。
  • 今回の問題では元の配列に目標値が存在していないので、幅2まで絞り込んでから近い方をreturn

解説付きコード

def minByBinarySearch(B, Alist, N):
  #二分探索
  left = 0
  right = N-1
  while right - left > 1:
    mid = (right + left) // 2
    if Alist[mid] > B:
      right = mid
    else:
      left = mid
  l_abs = abs(Alist[left] - B)
  r_abs = abs(Alist[right] - B)
  #近い方を判定
  if l_abs > r_abs:
    return r_abs
  else:
    return l_abs
 
def main():
  N = int(input())
  Alist = list(map(int, input().split()))

　　　　#二分探索を使いたいので配列をソート
  A_sort = sorted(Alist)
  Q = int(input())
 
  for i in range(Q):
    B = int(input())
    print(minByBinarySearch(B, A_sort, N))
 
main()