概要

商品の初期在庫が与えられた後、\(M\) 件の出荷依頼が順番に届くので、在庫が足りる場合のみ出荷を行うシミュレーションを行い、成功した件数を数える問題です。

考察

この問題は、問題文の指示通りに順番に出荷処理をシミュレーションすることで解くことができます。

シミュレーションを行う上で、「商品 \(F_j\) の現在の在庫数」をいかに早く確認・更新できるかがポイントになります。 もし、各依頼に対して「商品 \(1\) から商品 \(N\) まで順番に見て、商品番号が \(F_j\) と一致するものを探す」という処理をしてしまうと、1回の依頼につき最大 \(N\) 回の確認が必要となり、全体で \(O(NM)\) の時間がかかってしまいます。制約は \(N, M \leq 2 \times 10^5\) なので、これでは実行時間制限（TLE）に引っかかってしまいます。

これを解決するためには、商品の在庫を配列（リスト）で管理し、商品番号を配列のインデックス（添字）として扱うことが重要です。配列のインデックスを指定してデータにアクセスする操作は \(O(1)\) （定数時間）で行えるため、すべての依頼を高速に処理することが可能になります。

アルゴリズム

1. 各商品の初期在庫を、長さ \(N\) の配列 R に格納します。
2. 出荷に成功した件数をカウントする変数 ans を用意し、0 で初期化します。
3. \(M\) 件の出荷依頼を順番に見ていきます。各依頼について以下の処理を行います。
   • 依頼された商品番号 \(F_j\) に対応する在庫 R[F_j] を確認します。
   • もし R[F_j] が要求数 \(S_j\) 以上（R[F_j] >= S_j）であれば、出荷成功です。在庫 R[F_j] から \(S_j\) を引き、ans に \(1\) を足します。
   • もし R[F_j] が \(S_j\) 未満であれば、出荷失敗なので何もしません。
4. すべての依頼を処理し終えた後の ans の値を出力します。

計算量

• 時間計算量: \(O(N + M)\) 初期在庫の配列を作成するのに \(O(N)\)、各依頼の処理はインデックスアクセスにより \(O(1)\) で行え、それを \(M\) 回繰り返すため \(O(M)\) です。全体で \(O(N + M)\) となり、制約下で十分に高速に動作します。
• 空間計算量: \(O(N + M)\) 在庫を管理するための配列に \(O(N)\) の空間を使用します。正解コードでは入力を一度にすべて読み込んでいるため、入力データの保持を含めて全体で \(O(N + M)\) の空間を使用しています。

実装のポイント

• 0-indexed と 1-indexed の変換 問題文では商品番号は \(1\) から \(N\) まで（1-indexed）となっていますが、Pythonをはじめとする多くのプログラミング言語の配列は \(0\) から始まります（0-indexed）。そのため、入力された商品番号 \(F\) から \(1\) を引いて F - 1 とすることで、配列の正しい位置にアクセスできます。

• 高速な入出力 入力されるデータの数が最大で \(6 \times 10^5\) 個程度（\(N + 2M + 2\) 個）になるため、input() を何度も呼ぶのではなく、sys.stdin.read().split() などの高速な入出力メソッドを使用することで、実行時間を大幅に短縮できます。

  ソースコード

import sys

def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    
    R = [int(x) for x in input_data[2:2+N]]
    
    ans = 0
    idx = 2 + N
    for _ in range(M):
        F = int(input_data[idx]) - 1
        S = int(input_data[idx+1])
        idx += 2
        
        if R[F] >= S:
            R[F] -= S
            ans += 1
            
    print(ans)

if __name__ == '__main__':
    main()

この解説は gemini-3.1-pro-thinking によって生成されました。