概要

倉庫の在庫を管理しながら、出荷依頼を順番に処理し、在庫が足りる場合のみ出荷を行い、成功した件数を数える問題です。

考察

この問題のポイントは以下の通りです。

• 各出荷依頼は順番通りに処理する必要があります。依頼の順序を変えることはできません。
• 出荷は「全数出荷」か「出荷しない」かの二択です。部分出荷はありません。
• 在庫が足りれば減らし、足りなければ何もしない、というシンプルなシミュレーションです。

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

各依頼について在庫の確認と更新は \(O(1)\) で行えるため、\(M\) 件の依頼を順に処理しても全体で \(O(N + M)\) です。\(N, M \leq 2 \times 10^5\) なので、これは十分高速です。

特別なアルゴリズムやデータ構造は不要で、愚直なシミュレーションがそのまま正解になります。

具体例で確認しましょう。

例えば、商品が 2 種類で初期在庫が \(R = [10, 5]\) のとき、依頼が以下のように来たとします：

成功した件数は 2 件です。依頼 2 は在庫 5 に対して 6 個要求しているため失敗し、依頼 4 は在庫 0 のため失敗します。

アルゴリズム

1. 各商品の在庫を配列 \(R\) に格納する。
2. \(M\) 件の依頼を順番に処理する。
   • 依頼 \(j\) について、商品 \(F_j\) の在庫 \(R[F_j]\) が \(S_j\) 以上なら、\(R[F_j]\) から \(S_j\) を引き、成功カウントを 1 増やす。
   • そうでなければ何もしない。
3. 最終的な成功カウントを出力する。

計算量

• 時間計算量: \(O(N + M)\)
  • 在庫の読み込みに \(O(N)\)、依頼の処理に \(O(M)\)（各依頼は \(O(1)\)）
• 空間計算量: \(O(N)\)
  • 在庫を保持する配列のサイズ

実装のポイント

• 入力の高速化: Python では sys.stdin.buffer.read() で一括読み込みすることで、大量入力時の速度を改善できます。標準の input() を \(M\) 回呼ぶと遅くなる場合があります。

• 1-indexed の配列: 商品番号が \(1\) から \(N\) なので、配列を \(N+1\) のサイズで確保し、インデックス \(1\) ～ \(N\) を使うと、商品番号をそのまま添字として使えて実装が楽になります。

• 在庫数と出荷数が最大 \(10^9\): Python では整数のオーバーフローを気にする必要はありませんが、C++ などでは int の範囲に注意が必要です。

  ソースコード

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    R = [0] * (N + 1)
    for i in range(1, N + 1):
        R[i] = int(input_data[idx]); idx += 1
    count = 0
    for _ in range(M):
        F = int(input_data[idx]); idx += 1
        S = int(input_data[idx]); idx += 1
        if R[F] >= S:
            R[F] -= S
            count += 1
    print(count)

main()

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