概要

在庫数が限られている倉庫において、順番に来る出荷依頼に対して在庫があれば出荷を行い、なければスキップする。最終的に何件の出荷が成功したかを求める問題。

考察

この問題は、単純なシミュレーションで解けることがすぐにわかります。
つまり、各出荷依頼について「指定された商品の現在の在庫が依頼数以上か？」をチェックし、条件を満たしていれば在庫を減らして成功件数を増やす、という処理を順に行えばよいのです。

しかし、いくつかのポイントがあります。

• インデックスの扱い: 入力では商品番号が \(1\)-indexed（1から始まる）で与えられるが、配列の添字は通常 \(0\)-indexed（0から始まる）なので、変換が必要です。
• 効率的な入力処理: Python で標準入力を一行ずつ読み込むと遅くなることがあります。特に制約が大きい場合（\(N, M \sim 2 \times 10^5\)）、sys.stdin.read や input().split() を使って一度に読み込むと高速になります。
• 部分出荷は認められない: 在庫が不足している場合は一切出荷せず、次の依頼に進むため、在庫管理は正確に行う必要があります。

これらの点を踏まえて、在庫をリストで管理し、各依頼を前から順に処理していく方針が有効です。

アルゴリズム

1. 入力をすべて一度に読み込み、商品の初期在庫数をリスト stock に格納します。
2. 各出荷依頼を順番に処理します：
   • 依頼で指定された商品番号 \(F_j\)（1-indexed）を 0-indexed に変換します。
   • その商品の現在の在庫 stock[F_j] が依頼数 \(S_j\) 以上かを確認します。
   • 在庫があれば在庫を減らし、成功カウントを増やします。
3. 最終的に成功カウントを出力します。

この方法で、各依頼を定数時間で処理できるため、全体でも十分高速に動作します。

計算量

• 時間計算量: \(O(N + M)\)
  （入力を読み込むのに \(O(N + M)\)、各依頼を処理するのに \(O(1)\) なので全体で線形）
• 空間計算量: \(O(N + M)\)
  （在庫情報と入力データを保持するのに必要なメモリ）

実装のポイント

• 入力の商品番号は1-indexedなので、内部で扱うときは必ず0-indexedに変換すること（-1する）。

• 大量の入力を高速に処理するために、sys.stdin.read または input().split() を使う。

• 在庫の更新は単純な引き算で行えるので、条件分岐さえ正しければバグりにくい。

  ソースコード

import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    M = int(data[1])
    
    # 在庫リスト
    R = list(map(int, data[2:2+N]))
    
    # 在庫を管理するためのリスト（0-indexed）
    stock = R[:]
    
    success_count = 0
    
    # 出荷依頼を順に処理
    idx = 2 + N
    for _ in range(M):
        F = int(data[idx]) - 1  # 0-indexedにするために-1
        S = int(data[idx+1])
        idx += 2
        
        if stock[F] >= S:
            stock[F] -= S
            success_count += 1
    
    print(success_count)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。