概要

\(N\) 個の倉庫に対して \(M\) 回の荷物の出し入れを行い、すべての作業が終了した時点で「現在の荷物量 \(W_i\)」が「容量上限 \(L_i\)」を厳密に超えている倉庫の数を求める問題です。

考察

この問題で重要な点は、「すべての作業が終わった後の最終的な状態だけを確認すればよい」ということです。

作業の途中で一時的に容量を超えても、最終的に荷物を搬出して上限以下になればカウントしません。逆に、最初は上限以下でも、最終的に超えていればカウントします。

効率的な処理

制約を見ると \(N\) と \(M\) が最大で \(2 \times 10^5\) と大きいため、効率的な処理が必要です。 1. データの保持: 各倉庫の「現在の荷物量」と「容量上限」を配列（Pythonではリスト）で管理します。 2. 更新作業: 各作業 \(j\) では、指定された倉庫 \(P_j\) の荷物量に \(C_j\) を加算するだけです。これは \(1\) 回あたり \(O(1)\) で終わります。 3. 最終判定: 全作業終了後に \(N\) 個の倉庫を一つずつ確認します。これは \(O(N)\) で終わります。

もし、作業のたびに全倉庫の状態を確認していると、\(O(N \times M)\) の時間がかかってしまい、今回の制約（合計 \(4 \times 10^{10}\) 回程度の計算）では制限時間内に終わりません。今回のシミュレーション手法であれば、全体で \(O(N + M)\) となり、十分に間に合います。

アルゴリズム

1. 倉庫の初期荷物量 \(W\) を格納する配列と、上限 \(L\) を格納する配列を用意します。
2. \(M\) 回の作業について、以下の処理を繰り返します。
   • 倉庫番号 \(P_j\) を \(0\) 始まりのインデックスに直す（\(P_j - 1\)）。
   • \(W[P_j - 1]\) に \(C_j\) を加算する。
3. カウンタを \(0\) に初期化し、各倉庫 \(i\) (\(0\) から \(N-1\)) について以下を確認します。
   • もし \(W[i] > L[i]\) ならば、カウンタを \(1\) 増やす。
4. 最終的なカウンタの値を出力します。

計算量

• 時間計算量: \(O(N + M)\)
  • データの読み込みに \(O(N)\)、作業のシミュレーションに \(O(M)\)、最後の判定に \(O(N)\) かかります。\(N, M \leq 2 \times 10^5\) なので、全体で約 \(4 \times 10^5\) 回程度の操作となり、高速に動作します。
• 空間計算量: \(O(N)\)
  • 各倉庫の荷物量と上限を保存するための配列に \(O(N)\) のメモリを使用します。

実装のポイント

• 高速な入出力: Pythonにおいて \(N, M\) が \(10^5\) を超える場合、input() を繰り返すと入力がボトルネックで遅くなることがあります。sys.stdin.read().split() を使って一括で読み込むことで、実行時間を大幅に短縮できます。

• 1-indexed から 0-indexed への変換: 問題文では倉庫番号が \(1\) から \(N\) で与えられますが、プログラムの配列は通常 \(0\) から始まるため、番号から \(1\) を引いてアクセスする必要があります。

• 比較演算子: 「容量上限を超えてしまう」という条件は「上限より大きい」という意味なので、>= ではなく > を使用します。

  ソースコード

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、空白（スペース、改行、タブ）で分割してトークンのリストを作成します。
    # N, M が最大 2*10^5 であるため、この方法は Python において非常に高速です。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # トークンを整数に変換するイテレータを作成します。
    # map は Python 3 ではイテレータを返すため、メモリ効率が良いです。
    it = map(int, input_data)
    
    # 倉庫の数 N と作業の回数 M を読み込みます。
    try:
        N = next(it)
        M = next(it)
    except StopIteration:
        return
    
    # 各倉庫の現在の荷物量 W と容量上限 L を格納するリストを初期化します。
    weights = [0] * N
    limits = [0] * N
    
    # 各倉庫の初期情報を読み込みます。
    for i in range(N):
        weights[i] = next(it)
        limits[i] = next(it)
        
    # M 回の荷物の搬入・搬出作業を処理します。
    for _ in range(M):
        p = next(it) - 1  # 倉庫番号は 1-indexed なので 0-indexed に変換します。
        c = next(it)
        weights[p] += c
        
    # すべての作業終了後に容量上限 L を超えている倉庫の個数をカウントします。
    # 「超える」は厳密に大きい（weights[i] > limits[i]）ことを指します。
    ans = 0
    for i in range(N):
        if weights[i] > limits[i]:
            ans += 1
            
    # 結果を出力します。
    sys.stdout.write(str(ans) + '\n')

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-preview によって生成されました。