いろはちゃんコンテストDay4 B - 叫び声
問題概要
(一定間隔で1つ先の駅にたどり着く電車を使う or 走る) ことを繰り返した時、駅1から駅M+1までの最短所要時間を求めよ。
解法
まず(というかこの考え方がほぼ答えだが)、例えば入力例1において説明されているステップの3番目の、「(駅2で)電車1を待つ(時刻5-時刻6)」という行動は最初から電車1に乗って駅2に来ていれば当然同じように時刻6に駅2に到達しているはずなので無意味である。
このことから考えると、最終的にいろはちゃんが取りうる全ての行動は、
・ある1本の電車のみを使用し、駅M+1に到達する(らくらく)
もしくは
・駅1から駅M+1までずっと走る(つかれそう)
のN+1パターンに集約できることが分かる。
よって、これらのN+1パターンの所要時間の最小値を求める処理を実装して、AC。実装軽め。O(N)。
