AtCoder ABC084 C - Special Trains

AtCoderに取り組んだ記録です。
AtCoder ProblemsのRecommendationsからピックアップして解いています。

問題ページ
https://atcoder.jp/contests/abc084/tasks/abc084_c

Point: 300
Difficulty: 893

考えたこと

t秒後に駅xにいる場合の次の駅までの最短時間は、以下で計算できる
・駅xの始発時間を経過していない場合
　-> (始発までの時間 - t) + 次の駅までの移動にかかる時間
・駅xの始発時間を経過している場合
　-> 次の発車までの時間 + 次の駅までの移動にかかる時間

tとxで、x+1に到着するのは何秒後かは一意に算出できる。そのため、各駅の出発ごとに（x=0, 1, ... n-1）、t=0の状態から順次駅を進めていけば、最短の時間が算出できる。
駅の数は500以下なので、最大でも500*500回の計算ですむ。

ということで、実装して提出してみたらACでした。

提出したコード

提出ページ

package main

import (
	"bufio"
	"fmt"
	"os"
)

type station struct {
	c int
	s int
	f int
}

func main() {
	r := bufio.NewReader(os.Stdin)
	var n int
	fmt.Fscan(r, &n)

	st := make([]station, n-1)
	for i := 0; i < n-1; i++ {
		fmt.Fscan(r, &st[i].c)
		fmt.Fscan(r, &st[i].s)
		fmt.Fscan(r, &st[i].f)
	}

	w := bufio.NewWriter(os.Stdout)
	defer w.Flush()
	for i := 0; i < n; i++ {
		// 各駅からスタート
		t := 0
		for j := i; j < n-1; j++ {
			if t < st[j].s {
				t += (st[j].s - t) + st[j].c
			} else {
				tmp := (t - st[j].s) % st[j].f
				if tmp == 0 {
					t += st[j].c
				} else {
					t += (st[j].f - tmp) + st[j].c
				}
			}
		}
		fmt.Fprintln(w, t)
	}
}

感想など

・「SiはFiで割り切れることが保証されます」という条件は、どこに効いてくるものだったんだろう