Pythonで蟻本3-1 - 二分探索

背景：蟻本をやります - 競プロはじめました
テキスト：

プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～

【2021.05.05〜05.06】

lower_bound

mid を整数にするため，mid = (lb + ub) // 2 とします．
【入力】

5
2 3 3 5 6
3

【出力】

1

【コード】

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

# upper bound, lower bound
lb, ub = -1, n

while ub - lb  > 1:
  mid = (lb + ub) // 2
  if a[mid] >= k:
    ub = mid
  else:
    lb = mid
    
print(ub)

bisectを使う方法．
bisect --- 配列二分法アルゴリズム — Python 3.9.4 ドキュメント
Python標準ライブラリ：順序維持のbisect - Qiita

【コード】

from bisect import bisect_left

n = int(input())
a = list(map(int, input().split()))
k = int(input())
    
print(bisect_left(a, k))

Cable master

最近見た問題だと，以下がありました：
C - MAD TEAM | ZONeエナジー プログラミングコンテスト “HELLO SPACE”

今回は，midは整数でなくて良いので，mid = (lb + ub)/2 とします．
【入力】

4 11
8.02 7.43 4.57 5.39

【出力】

2.00

【コード】

import math

n, k = map(int, input().split())
l = list(map(float, input().split()))
    
def c(x):
  num = 0
  for i in range(n):
    num += l[i]//x
  return num >= k

lb, ub = 0, 1e5 + 1
for _ in range(100):
  mid = (lb + ub)/2
  if c(mid):
    lb = mid
  else:
    ub = mid

print(format(math.floor(ub*100)/100, '.2f'))

小数点以下2桁までを切り捨てるため，①×100で2桁増やしたあとでfloor (床関数) で小数点以下を切り捨て，②÷100で桁を戻しています．
【参考】床関数・天井関数と関係式 - Notes_JP

メモ：何か，良い関数はない？

Aggressive cows

crtはcurrent (現在)の略と思われます．
【入力】

5 3
1 2 8 4 9

【出力】

3

【コード】

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

def c(d):
  last = 0  # 1頭目の位置はx[0]
  for _ in range(1, m):
    # 2~m頭目
    crt = last + 1
    while crt < n and x[crt] - x[last] < d:
      crt += 1
    if crt == n:
      return False
    last = crt
  # 上のifで抜けなかったらTrue
  return True

lb, ub = 0, 10**9 + 1
while ub - lb > 1:
  mid = (lb + ub)//2
  if c(mid):
    lb = mid
  else:
    ub = mid
    
print(lb)

平均最大化

【入力】

3 2
2 2
5 3
2 1

【出力】

0.75

【コード】

n, k = map(int, input().split())
w, v = [], []
for _ in range(n):
  wi, vi = map(int, input().split())
  w.append(wi)
  v.append(vi)

def c(x):
  y = sorted([vi - x*wi for wi, vi in zip(w, v)], reverse=True)
  return sum(y[:k]) >= 0

# upper bound, lower bound
lb, ub = 0, 10**6 + 1

for _ in range(100):
  mid = (lb + ub) / 2
  if c(mid):
    lb = mid
  else:
    ub = mid
    
print(round(lb, 2))