Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 223 C 問題 Doukasen

AtCoder ABC ABC223 C問題 300 pts

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

N 本の導火線を一本につなげた導火線で, 左から i 番目の導火線は長さ A_i で, 秒速 B_i で燃える.

両端から同時に火をつけたとき, この2つの火がぶつかるのは地点の左端からどのくらい離れた点かを求めよ.

制約

  • 1 \leq N \leq 10^5
  • 1 \leq A_i, B_i \leq 1000

解法

片方のみからつけた場合, \displaystyle \sum_{i=1}^N \dfrac{A_i}{B_i} で完全に燃え尽きる. このことから, 両端に火をつけた場合は \displaystyle T:=\dfrac{1}{2} \sum_{i=1}^N \dfrac{A_i}{B_i} 秒後に2つの火がぶつかる.

よって, T 秒間で左側の火が進む長さ L を求められれば良い. これは以下のような単純なシミュレーションで求めることができる.

  • t=0 とする.
  • i=1,2,\dots,N の順に以下を実行する.
    • t+\frac{A_i}{B_i} \leq T ならば, L に A_i を加算する (左の火は i 番目の導火線を燃やし切る).
    • t \leq T \lt t+\frac{A_i}{B_i} ならば, L に B_i (T-t) を加算する (途中で左右の火がぶつかる).
    • t に \frac{A_i}{B_i} を加算する.