ABC223C - Doukasen

考え方：二分探索

バグ取りに苦労した．もっと見通しの良い方法がありそう．

求める位置が左からx以上となるならok，そうでないならngとして二分探索を考える．

あとはcheck(x)関数をつくればよい．左からx進むのにかかる時間tlと，トータルの時間を計算することができる．右からxの地点までかかる時間trは，「(トータルの時間) - (左からx進むのにかかる時間)」で求められる．このとき，tl <= trならTrue（求める位置はx以上），そうでないならFalseである．

ただし，左から1コ目の導火線でぶつかる場合に注意．

import itertools, bisect

N = int(input())
AB = [list(map(int, input().split())) for _ in range(N)]
T = [a / b for a, b in AB]
Tacc = list(itertools.accumulate(T))
Ttot = Tacc[-1]

L = [a for a, b in AB]
Lacc = list(itertools.accumulate(L))
Ltot = Lacc[-1]

def check(x):
  i = bisect.bisect_left(Lacc, x)

  tl = x / AB[i][1]
  if i > 0:    
    tl = Tacc[i - 1] + (x - Lacc[i - 1]) / AB[i][1]
  tr = Ttot - tl
  if tl <= tr:
    return True
  else:
    return False

ok = 0
ng = Ltot

while abs(ng - ok) > 1e-7:
  mid = (ng + ok) / 2
  if check(mid):
    ok = mid
  else:
    ng = mid
    
print(ok)