ABC 084 Special Trains

問題

C - Special Trains

前に解いたときにACできなかったのでリベンジです

考察

ある駅iに着いたとき,開通式開始後からかかった時間がTとすると,

  • T>= S_i なら,F_i間隔で走っている電車が来るまで待つ.待ち時間は,T % F_i = 0なら「0」,T % F_i ≠ 0なら「F_i-T%F_i」である.
  • T< S_i なら,まだiからの電車は走り始めていないので,待ち時間はS_i-Tである.

以上の待ち時間に,次の駅までかかる時間C_iを加えたものを足していけば,求める答えとなる.

計算量的にもO(N2)で間に合う.

コード

https://beta.atcoder.jp/contests/abc084/submissions/2874094

反省

時間測ってませんでしたがリベンジ後1発AC

  • 改めて解いてみると過去の自分がなんでできなかったのかわからない.成長したということか.
  • 基本的に解説通りだったし特に言うことはない