概要

受付窓口で \(N\) 人の来客に順番に対応するとき、最後の来客への対応が終了する時刻を求めるシミュレーション問題です。

考察

この問題の核心は、各来客の対応開始時刻 \(S_i\) がどう決まるかを理解することです。

来客 \(i\) の対応が始まるのは、次の 2つの条件が両方満たされた瞬間 です： 1. 前の来客 \(i-1\) への対応が終わっている（窓口が空いている） 2. 来客 \(i\) が到着済みである

つまり、対応開始時刻は以下のようになります：

\[S_i = \max(S_{i-1} + B_{i-1},\ A_i)\]

具体例で理解する

例えば \(N = 3\) で以下の入力を考えます：

来客	到着時刻 \(A_i\)	対応時間 \(B_i\)
1	0	5
2	3	3
3	10	2

• 来客1：時刻 \(0\) に到着、対応開始 \(S_1 = 0\)、対応終了 \(0 + 5 = 5\)
• 来客2：時刻 \(3\) に到着しているが、窓口は時刻 \(5\) まで埋まっている → \(S_2 = \max(5, 3) = 5\)、対応終了 \(5 + 3 = 8\)
• 来客3：時刻 \(10\) に到着、窓口は時刻 \(8\) に空いている → \(S_3 = \max(8, 10) = 10\)、対応終了 \(10 + 2 = 12\)

答えは \(12\) です。来客2のように「到着したが窓口が空いていない」場合は待ち、来客3のように「窓口は空いているが来客が未到着」の場合は到着を待つことになります。

素朴なアプローチで十分か？

この問題は漸化式を前から順に計算するだけで解けます。各来客について \(O(1)\) の計算なので、特別な高速化は不要です。

アルゴリズム

変数 \(S\) で「現在の窓口が空く時刻（＝直前の来客への対応終了時刻）」を管理します。

1. \(S = 0\) で初期化する（窓口は時刻 \(0\) から対応可能）
2. 各来客 \(i\) について：
   • 対応開始時刻は \(\max(S, A_i)\)（窓口が空く時刻と到着時刻の大きい方）
   • 対応終了時刻は \(\max(S, A_i) + B_i\)
   • \(S\) をこの対応終了時刻に更新する
3. 全来客を処理した後の \(S\) が答え

これをコードにすると、ループ内の処理は：

S = max(S, A) + B

というたった1行の更新になります。

計算量

• 時間計算量: \(O(N)\) — 各来客について \(O(1)\) の処理を \(N\) 回行う
• 空間計算量: \(O(1)\) — 変数 \(S\) のみで管理（入力の読み込みを除く）

実装のポイント

• \(A_i\) と \(B_i\) が最大 \(10^9\) であり、\(N\) が最大 \(2 \times 10^5\) なので、対応終了時刻は最大で約 \(2 \times 10^{14}\) 程度になりえます。C++ などでは long long を使う必要がありますが、Python では整数のオーバーフローを気にする必要はありません。

• 変数 \(S\) は「現在の窓口が空く時刻」という意味を持ちます。初期値を \(0\)（窓口が最初から空いている）とすることで、来客1に対しても同じ式 S = max(S, A) + B で統一的に処理できます。

  ソースコード

N = int(input())
S = 0
for _ in range(N):
    A, B = map(int, input().split())
    S = max(S, A) + B
print(S)

---

この解説は claude4.6opus-thinking によって生成されました。