atcoder ABC 319 E - Bus Stopsの勉強

クエリ atcoder

atcoder.jp

・参考
ABC319をPythonで解いてみたよ。(A～E問題) - Qiita

・説明
　TLEだったので、参考記事を参考にした。プログラムの説明は下のプログラムでコメントアウトしている。

import math
n,x,y=map(int,input().split())
p=[]
t=[]
for i in range(n-1):
    pi,ti=map(int,input().split())
    p.append(pi)
    t.append(ti)
    
LCM=math.lcm(*[i for i in range(1,9)])  #1-8までの最大公倍数.840.

ans=[0 for _ in range(LCM)]

#前もって、840までの問題文の答えを用意してansに代入する.
for i in range(LCM):
    ni=i+x   #バス停1につくまで.
    #バスの乗り継ぎ時間.
    for j in range(n-1):
        if ni%p[j]==0:
            ni+=t[j]
        else:
            quo=ni//p[j]  #商.
            ni=p[j]*(quo+1)+t[j]
    #バス停から青木君の家につくまでの時間.
    ni+=y   
    ans[i]=ni
    

q=int(input())
for _ in range(q):
    qi=int(input())
    quo, MOD=divmod(qi, LCM)
    print(ans[MOD]+LCM*quo)  #例えば、qi=847だとquo=1, MOD=7より、qiが7の答えにLCM*1(LCMで区切られるので)を足す.