AtCoder練習記録#2

二分探索について学ぶ

二分探索とは

二分探索はその名の通り，「二分する」，つまり候補を半分にしながら探索していくアルゴリズムです．自分は院試で勉強済みなのでここでの解説は省略。
詳しくはこちらを参考

今回解く問題

こちら

自分が初めに提出したコード

自分が考えたやつ

n,m = map(int,input().split())
a = list(map(int,input().split()))

if sum(a) <= m:
  print("infinite")
else:
  for i in range(max(a)-1,0,-1):
    if sum(min(i,x) for x in a) <= m:
      print(i)
      break

結果

時間超過によって0点!!!

ということで二分探索を使って解いていきましょう。

二分探索バージョン

n,m = map(int,input().split())
a = list(map(int,input().split()))

def binary_search(n,m,a):
  if sum(a) <= m:
    return "infinite"

  # 二分探索
  left,right = 0,max(a)
  result = 0
  while left<=right:
    mid = (left + right) // 2
    total = sum(min(mid,ai) for ai in a)

    if total <= m:
      result = mid
      left = mid +1
    else:
      right = mid - 1
  return result

print(binary_search(n,m,a))

結果

行けました。二分探索は実装も簡単なので次解くときは秒殺できるように頑張ります。