AtCoder-ABC214 C - Distribution【Python解答例】

AtCoder Beginner Contest214のC問題についてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 214 - AtCoder

AtCoder Beginner Contest214 C - Distribution

C - Distribution

問題文

N 人のすぬけ君が円周上に並んでおり、反時計回りに 1,2,...,N の番号がついています。

i(1 ≤ i ≤ N) 番目のすぬけ君は時刻 t に宝石をもらうと Si 単位時間後、すなわち時刻 t+Si にその宝石を (i + 1) 番目のすぬけ君に渡します。ただし、(N+1) 番目のすぬけ君とは 1 番目のすぬけ君のことを指すとします。

また、高橋君は時刻 Ti に i 番目のすぬけ君に宝石を渡します。

全ての i(1 ≤ i ≤ N) について、i 番目のすぬけ君が初めて宝石をもらう時刻を求めてください。なお、宝石の受け渡しにかかる時間は無視できるものとします。

制約

・1 ≤ N ≤ 200000
・1 ≤ Si,Ti ≤ 10^9
・入力は全て整数である。

解答例

n = int(input())

S = list(map(int, input().split()))
T = list(map(int, input().split()))

for i in range(2*n):
    T[(i+1) % n] = min(T[(i+1) % n], T[i % n] + S[i % n])

for i in range(n):
    print(T[i])

解説

N人のすぬけ君が それぞれ初めて宝石をもらう時間を答える問題です。

i+1番目のすぬけ君がはじめて宝石をもらうのは、Ti+1時間に高橋くんから宝石をもらうか、i 番目のすぬけ君から宝石をもらうか、どちらか早いほうになります。

したがって、T[i+1]かT[i]+S[i]のうち小さいほうがもとめる時間です。
この小さいほうをT[i+1]に格納していくことで、Tが最も早く宝石をもらえる時間として更新されていきます。

この更新を2周させることでN人のすぬけ君が宝石をもらえる時間が求まります。
1人目のすぬけ君がはじめて宝石をもらえるのは、高橋くんからもらえるT[0]か、N人目のすぬけ君が宝石をもらえる時間のどちらか早いほうです。
N人目のすぬけ君が宝石をもらえる時間を求めるために1周させて、さらに1人目のすぬけ君のはじめて宝石をもらえる時間が2周目に更新されます。
2周させることでTが最も早く宝石がもらえる時間となります。

最後にTの各要素を出力していけばACでした。

ABC214の関連記事はこちら
ebisuke33.hatenablog.com