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で割り切れることが保証されます」という条件は、どこに効いてくるものだったんだろう
この記事が気に入ったらサポートをしてみませんか?