概要

来客を番号順に1人ずつ処理していく「1本の待ち行列シミュレーション」です。
窓口が次に空く時刻を更新し続ければ、最後の来客の終了時刻をそのまま求められます。

考察

重要な点は、各来客 \(i\) の開始時刻が
\(S_i = \max(\text{前の来客の終了時刻}, A_i)\)
で決まることです。

つまり、その時点で管理すべき情報は「窓口が空く時刻」だけです。
これを end_time とすると、来客 \((A_i, B_i)\) に対して

1. まだ来客が来ていないなら待つ：end_time = max(end_time, A_i)
2. 対応時間 \(B_i\) だけ進める：end_time += B_i

で、来客 \(i\) の終了時刻になります。

---

素朴に「各時刻を1ずつ進める」ようなシミュレーションをすると、時刻が最大で \(10^9\) オーダーなので到底間に合いません。
また、各来客について「いつ開始できるか」を過去全体から毎回探す必要もなく、直前までの結果（窓口が空く時刻）だけで十分です。
この1変数更新に落とし込むことで、\(N\) 回のループだけで解けます。

---

例えば

• 来客1: \((A_1,B_1)=(2,3)\)
  
• 来客2: \((A_2,B_2)=(2,4)\)
  
• 来客3: \((A_3,B_3)=(10,1)\)

とすると、

• 初期 end_time=0
• 来客1: max(0,2)=2, then +3 で 5
• 来客2: max(5,2)=5, then +4 で 9
• 来客3: max(9,10)=10, then +1 で 11

よって答えは 11 です。

アルゴリズム

1. end_time = 0 で初期化する（窓口が空いている時刻）。
2. 来客を \(1\) 人目から \(N\) 人目まで順に読む。
3. 各来客 \((A, B)\) について:
   • end_time = max(end_time, A)
     （来客到着前なら待機）
   • end_time += B
     （対応して終了時刻へ進める）
4. ループ終了後の end_time を出力する。これが最後の来客の終了時刻。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\)

実装のポイント

• 制約が大きいので、Pythonでは sys.stdin.readline を使うと安定して高速です。

• 時刻は最大でおおよそ \(10^9 + N \cdot 10^9\) まで伸びうるため、言語によっては 64bit 整数が必要です（Python は多倍長整数なので問題なし）。

• A_i は単調非減少ですが、この解法ではその性質に依存しすぎず、順番通り処理するだけで正しく動作します。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    end_time = 0  # current time when counter becomes free

    for _ in range(N):
        A, B = map(int, input().split())
        if end_time < A:
            end_time = A
        end_time += B

    print(end_time)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.3-codex によって生成されました。