概要

\(N\) 種類の本の在庫を管理し、\(M\) 件の貸出申請を時系列順に処理するシミュレーション問題です。各申請に対して「在庫が足りるか」を判定し、足りる場合のみ在庫を減らします。

考察

この問題のポイントは、「申請を順番に処理する」ことと、「在庫が足りない場合は何もしない」という条件を正確にプログラムに落とし込むことです。

1. シミュレーションの実行: 各本の現在の在庫数は、配列（Pythonではリスト）を使って管理するのが効率的です。管理番号 \(i\) の本の在庫を A[i-1]（0-indexedの場合）に格納しておけば、各申請に対して \(O(1)\) で在庫の参照と更新が可能です。
2. 制約の確認: \(N\) と \(M\) が最大で \(10^5\) であるため、全申請を順番に処理しても計算回数は \(10^5\) 回程度です。これは一般的なプログラミング言語で 1 秒間に処理できる計算量（約 \(10^8\) 回）の範囲内に十分収まります。
3. 高速な入出力: 入力の件数が多いため、Pythonで input() を何度も呼び出すと実行時間制限（TLE）に間に合わない可能性があります。sys.stdin.read().split() などを用いて一括で入力を読み込む工夫が有効です。

アルゴリズム

1. 各本の初期在庫数 \(A_1, A_2, \dots, A_N\) を配列 A に格納します。
2. \(M\) 件の貸出申請 \((B_j, C_j)\) を一つずつ順番に読み込みます。
3. 管理番号 \(B_j\) に対応する現在の在庫 A[B_j - 1] を確認します。
   • A[B_j - 1] >= C_j であれば、在庫を \(C_j\) 減らします（A[B_j - 1] -= C_j）。
   • そうでなければ、その申請はスキップします。
4. すべての申請を処理した後、配列 A の内容を順番に出力します。

計算量

• 時間計算量: \(O(N + M)\)
  • 初期在庫の読み込みに \(O(N)\)、申請の処理に \(O(M)\) かかります。
• 空間計算量: \(O(N)\)
  • \(N\) 種類の本の在庫数を保持するための配列が必要です。

実装のポイント

• 0-indexed への変換: 問題文では本の管理番号が \(1\) から \(N\) で与えられますが、プログラムの配列は通常 \(0\) から始まるため、B_j - 1 としてインデックスを調整する必要があります。

• Python での高速化: sys.stdin.read().split() を使うことで、大量の数値を一括でリストとして取得でき、読み込み時間を大幅に短縮できます。また、出力時に *A と記述することで、リストの要素をスペース区切りで簡潔に展開して出力できます。

  ソースコード

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、空白で分割してリストにする
    # sys.stdin.read().split() は大量の入力を高速に読み込む際に有効です
    input_data = sys.stdin.read().split()
    
    # 入力が空の場合は終了
    if not input_data:
        return
    
    # 本の種類数 N と貸出申請の件数 M を取得
    N = int(input_data[0])
    M = int(input_data[1])
    
    # 各本の初期蔵書数 A_1, ..., A_N を取得
    # 管理番号 i の本は 0-indexed で A[i-1] に対応させる
    A = list(map(int, input_data[2:N+2]))
    
    # 貸出申請の処理
    # 貸出申請の情報は input_data[N+2] 以降に B_j, C_j のペアで格納されている
    ptr = N + 2
    for _ in range(M):
        # 管理番号 B_j と貸出希望冊数 C_j
        b_j = int(input_data[ptr])
        c_j = int(input_data[ptr+1])
        ptr += 2
        
        # 0-indexed に変換した管理番号
        idx = b_j - 1
        
        # 蔵書数が申請された冊数以上の場合は貸し出しを実行
        if A[idx] >= c_j:
            A[idx] -= c_j
            
    # すべての申請を処理した後の蔵書数を管理番号 1 から N の順にスペース区切りで出力
    # print(*A) はリストの要素をスペース区切りで展開して出力する
    print(*(A))

if __name__ == '__main__':
    solve()

---

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