[AtCoder]ABC 084 C-Special Trains

AtCoder

Photo by Pixabay on Pexels.com

2022.05.072022.05.02

問題
方針
解答
提出結果
感想

問題

C - Special Trains

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

方針

\(N = 500\)なので\(O(N^2)\)でも間に合う。駅\(i\ \ (1\leq i\leq N)\)に対して時間\(t\)を考える。駅\(i\)に到達したとき、時間\(t < S_i\)であれば、\(S_i\)まで待つ必要があるので、\(t = S_i\)になる。そうでなく、\(t > S_i\)のときは、到達した時間\(t\)が\(F_i\)で割り切れるかどうかで場合分けが生じる。割り切れるとき、何もしなくてよい（continueにしてはいけない。for loopの中でcontinueにすると以下がskipされてしまう）。割り切れないときは、時間\(t\)に\(F_j-t\%F_j\)を追加してやる。

解答

#atcoder template
def main():
    import sys
    input = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    n = int(input())
    c, s, f = [0]*n, [0]*n, [0]*n
    for i in range(n-1):
        c[i], s[i], f[i] = map(int, input().split())
    #output
    import math
    for i in range(n):
        t = 0
        for j in range(i, n-1):
            if t < s[j]:
                t = s[j]
            elif t%f[j] == 0:
                temp = 0
            else:
                t += f[j]-t%f[j]
            t += c[j]
        print(t)
    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()