AtCoder Beginner Contest 214 [ C - Distribution ]をPythonで解く（300点、⬜️灰色diff）

問題

atcoder.jp

問題概要

N人が円周上に並んでいる．
i番目の人は時刻tに宝石をもらうとSi時間後にその宝石を(i+1)番目の人に渡す．
ただし，(N+1)=1とする．
また，高橋君は時刻Tiにi番目の人に宝石を渡す．
すべてのiについて，i番目の人が初めて宝石をもらう時刻を求めよ．

1≤N≤2×10⁵
1≤Si, Ti≤10⁹
(問題概要かんプリンさんサイトより引用)

解法

1 <= iのi番目すぬけ君について考える。
宝石を渡されるパターンは２つ考えられる。

• 隣のすぬけ君から宝石を渡される。
• 自分担当の高橋くんから宝石を渡される。

なので、このどちらかの小さい方が答え。

しかし円周上に、すぬけ君が並んでいるのがポイントで、１周だけループさせただけでは答えが出ない。
最低２周させる必要がある。

２周対応にするために、配列の添字はNで割った余りに。

実装

参考

atcoder.jp

少なくとも 2N 回ループを回さないといけないことに注意してください。