概要

\(N\) 個の倉庫に対して \(M\) 回の搬入・搬出作業を行った後、容量上限を超えている倉庫の数を数える問題です。

考察

問題の整理

この問題では、各倉庫について以下の情報が与えられます： - 現在の荷物量 \(W_i\) - 容量上限 \(L_i\)

そして \(M\) 回の作業で、指定された倉庫の荷物量が増減します。最終的に \(W_i > L_i\) となる倉庫の数を求めます。

重要な気づき

この問題のポイントは「作業の途中経過は気にしなくてよい」ということです。問われているのはすべての作業終了後の状態のみなので、各倉庫に対する荷物の変動量を合計するだけで十分です。

素朴なアプローチで問題ないか

各作業を順番にシミュレーションする方法は： - \(M\) 回の作業を処理：\(O(M)\) - 最終的に \(N\) 個の倉庫をチェック：\(O(N)\)

合計 \(O(N + M)\) となり、\(N, M \leq 2 \times 10^5\) の制約下では十分高速に動作します。

具体例

例えば、倉庫1の初期荷物量が \(W_1 = 50\)、容量上限が \(L_1 = 100\) だとします。

作業として： - 倉庫1に +30 搬入 - 倉庫1から -10 搬出 - 倉庫1に +40 搬入

が行われると、最終的な荷物量は \(50 + 30 - 10 + 40 = 110\) となり、\(110 > 100\) なので容量上限を超えています。

アルゴリズム

1. 入力の読み込み: 各倉庫の初期荷物量 \(W_i\) と容量上限 \(L_i\) を配列に格納する
2. 作業のシミュレーション: \(M\) 回の作業について、対象倉庫 \(P_j\) の荷物量に \(C_j\) を加算する
3. カウント: すべての倉庫について、\(W_i > L_i\) を満たす倉庫の数を数える
4. 出力: カウント結果を出力する

計算量

• 時間計算量: \(O(N + M)\)
  • 倉庫情報の読み込み：\(O(N)\)
  • 作業の処理：\(O(M)\)
  • 最終チェック：\(O(N)\)
• 空間計算量: \(O(N)\)
  • 各倉庫の荷物量と容量上限を保存する配列

実装のポイント

1. 1-indexed の扱い: 倉庫番号は \(1\) から \(N\) までなので、配列を \(N+1\) のサイズで確保し、インデックス \(1\) から使用すると便利です。

2. 大きな値に注意: \(W_i\) や \(C_j\) は最大 \(10^9\) のオーダーで、累積すると大きな値になる可能性があります。Python では整数のオーバーフローを気にする必要はありませんが、他の言語では64ビット整数型を使用しましょう。

3. 高速な入力: \(N, M\) が大きい場合、sys.stdin.readline を使うことで入力処理を高速化できます。

   ソースコード

def main():
    import sys
    input = sys.stdin.readline
    
    N, M = map(int, input().split())
    
    W = [0] * (N + 1)
    L = [0] * (N + 1)
    
    for i in range(1, N + 1):
        w, l = map(int, input().split())
        W[i] = w
        L[i] = l
    
    for _ in range(M):
        p, c = map(int, input().split())
        W[p] += c
    
    count = 0
    for i in range(1, N + 1):
        if W[i] > L[i]:
            count += 1
    
    print(count)

if __name__ == "__main__":
    main()

---

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