概要

各商品の在庫数を管理しながら、出荷依頼を順番に処理して「在庫が足りた依頼の数」を数える問題です。

考察

重要なのは、各依頼はその時点の在庫だけで成功・失敗が決まり、成功したときだけ在庫が減ることです。失敗した依頼は在庫が減らず、後からやり直しもありません。

このルールから、やるべきことは単純で、

• 依頼 \((F_j, S_j)\) が来たら、在庫 \(R_{F_j}\) を見て
  • \(R_{F_j} \ge S_j\) なら成功：\(R_{F_j} \leftarrow R_{F_j} - S_j\)
  • そうでなければ失敗：何もしない
• 成功した回数を数える

だけです。

素朴に「毎回在庫を探す」こと自体は必要ですが、商品番号が直接与えられるので、配列で在庫を持てば 1 回の依頼につき \(O(1)\) で処理できます。逆に、在庫を毎回別の方法で探したり（例：リストから商品を検索するなど）すると、最悪で \(O(NM)\) になり \(N, M \le 2 \times 10^5\) では間に合いません。

また入力量が大きいので、Python では入力を sys.stdin.buffer.read() でまとめて読むなど、高速入力が有効です。

具体例： - 在庫 \(R = [5, 2]\) - 依頼：(商品1を3個) → \(5 \ge 3\) 成功、在庫は \([2,2]\) - 依頼：(商品1を4個) → \(2 < 4\) 失敗、在庫は変わらず \([2,2]\) - 依頼：(商品2を2個) → \(2 \ge 2\) 成功、在庫は \([2,0]\) 成功数は 2 件です。

アルゴリズム

1. 配列 R に各商品の在庫数を保持する（0-index にする）。
2. 依頼を先頭から順に処理する：
   • f を商品番号（0-index）、s を出荷数量とする。
   • もし R[f] >= s なら R[f] -= s して成功数 ans を 1 増やす。
   • そうでなければ何もしない。
3. 最後に ans を出力する。

計算量

• 時間計算量: \(O(N + M)\)（在庫の読み込み \(N\) 回＋依頼処理 \(M\) 回、各操作は定数時間）
• 空間計算量: \(O(N)\)（在庫配列）

実装のポイント

• 入力サイズが最大で大きいので、sys.stdin.buffer.read().split() のように高速に読み取ると安全です。

• 商品番号 \(F_j\) は \(1\) 始まりなので、配列アクセスのために -1 して \(0\) 始まりに変換します。

• 在庫や数量は最大 \(10^9\) ですが、減算と比較のみなので Python の int で問題ありません。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    M = next(it)
    R = [next(it) for _ in range(N)]
    ans = 0
    for _ in range(M):
        f = next(it) - 1
        s = next(it)
        if R[f] >= s:
            R[f] -= s
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()

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