概要

各商品の初期在庫数と順次届く出荷依頼が与えられ、在庫が十分な場合のみ出荷を成功させ、成功した依頼の件数を求める問題です。

考察

この問題は、各商品の在庫数を管理しながら、順番に届く出荷依頼を処理するシンプルなシミュレーション問題です。重要な点は、在庫が要求数量以上ある場合のみ出荷が成功し、在庫が減ることです。部分出荷は許されず、失敗した依頼は再処理されません。制約条件から、商品数Nと依頼数Mが最大20万個までありえるため、効率的な処理が必要です。

アルゴリズム

1. 各商品の初期在庫数を配列で保持する
2. 各出荷依頼を順番に処理する
3. 依頼ごとに、対象商品の現在の在庫数を確認する
4. 在庫数が要求数量以上の場合：
   • 在庫数を要求数量分減らす
   • 成功カウントを1増やす
5. 在庫数が要求数量未満の場合：
   • 何もせず次の依頼に進む
6. 全ての依頼を処理後、成功カウントを出力する

計算量

• 時間計算量: \(O(M)\)
• 空間計算量: \(O(N)\)

実装のポイント

• 商品番号は1-indexedで与えられるため、配列アクセス時には0-indexedに変換する（f-1）

• 在庫管理用の配列を初期在庫配列からコピーして使用する

• 入力データの読み込みを効率的に行うため、sys.stdin.read()を使用する

• 各依頼の処理は単純な比較と減算のみなので、高速に処理できる

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        print(0)
        return
        
    n = int(data[0])
    m = int(data[1])
    R = list(map(int, data[2:2+n]))
    requests = []
    index = 2 + n
    for i in range(m):
        f = int(data[index])
        s = int(data[index+1])
        index += 2
        requests.append((f, s))
    
    stock = R[:]
    success_count = 0
    
    for f, s in requests:
        idx = f - 1
        if stock[idx] >= s:
            stock[idx] -= s
            success_count += 1
            
    print(success_count)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。