日刊競プロ ABC 223 - C - Doukasen-

C - Doukasen

問題文
N 本の導火線を一直線に接着したものがあります。左から i 本目の導火線は長さが Aicm で、 1 秒あたり Bicm の一定の速さで燃えます。この導火線の左端と右端から同時に火をつけるとき、 2 つの火がぶつかる場所が着火前の導火線の左端から何 cm の地点か求めてください。

制約
1≤N≤10**5
1≤Ai,Bi​≤1000
入力は全て整数

考えたこと

まず初めに片側から火をつけたときに、片方の端っこまで燃え尽きるにはどれだけ時間がかかるかを考える。キーポイントなのは両端から火をつけた場合はから火をつけたときの半分の時間でぶつかるということ。

両端で火をつけた場合の時間を求めたら、その時間でどれだけ導火線が進むかを考えれば良い。求めた時間よりA/Bが小さい時は距離Aを足していき、求めた時間より大きいときは速さ×時間を用いて、B×残りの時間で距離を足していく。

N = int(input())
AB = []
A = []
B = []
for _ in range(N):
 a,b = map(int,input().split())
 A.append(a)
 B.append(b)
time = 0
for i in range(N):
 time+=(A[i]/B[i])
time = time/2
ans = 0
for i in range(N):
 if time>=A[i]/B[i]:
   ans+=A[i]
   time-=A[i]/B[i]
 else:
   ans+=B[i]*time
   break
   
print (ans)