概要

\(N\) 種類の本の蔵書に対して \(M\) 件の貸出申請を順番に処理し、蔵書が足りない場合はスキップしながら、最終的な各本の蔵書数を求める問題です。

考察

この問題で重要な気づきは以下の通りです：

• 貸出申請は順番通りに処理する必要があります。ある申請をスキップするかどうかは、その時点での蔵書数に依存するためです。
• 例えば、管理番号 \(1\) の本が \(5\) 冊あるとき、「\(3\) 冊貸出」→「\(3\) 冊貸出」という申請が来た場合、1回目は成功して残り \(2\) 冊になり、2回目は蔵書不足でスキップされます。もし順序を無視すると結果が変わってしまいます。

素朴なアプローチとして、各申請に対して該当する本の蔵書数を確認し、足りていれば引くという処理を考えますが、これは実はそのまま十分高速です。各申請の処理は配列の1要素へのアクセスと比較・減算だけなので \(O(1)\) で済みます。

特別なデータ構造やアルゴリズムは必要なく、愚直にシミュレーションするだけで解けます。

アルゴリズム

1. 蔵書数の配列 \(A\) を読み込みます（\(A[0]\) が管理番号 \(1\) の本に対応）。
2. \(M\) 件の貸出申請を先頭から順に処理します：
   • 管理番号 \(B_j\) の本の現在の蔵書数 \(A[B_j - 1]\) が \(C_j\) 以上であれば、\(A[B_j - 1]\) から \(C_j\) を引きます。
   • そうでなければ何もしません（スキップ）。
3. すべての申請を処理した後、配列 \(A\) を出力します。

具体例（\(N=3\), \(A = [5, 3, 2]\)）： - 申請「管理番号1を3冊」→ \(A[0] = 5 \geq 3\) なので \(A[0] = 2\) に更新 - 申請「管理番号1を3冊」→ \(A[0] = 2 < 3\) なのでスキップ - 申請「管理番号2を2冊」→ \(A[1] = 3 \geq 2\) なので \(A[1] = 1\) に更新 - 最終結果：\([2, 1, 2]\)

計算量

• 時間計算量: \(O(N + M)\)
  • 配列の初期化に \(O(N)\)、\(M\) 件の申請処理にそれぞれ \(O(1)\) で合計 \(O(M)\)
• 空間計算量: \(O(N)\)
  • 蔵書数を格納する配列のサイズ

\(N, M \leq 10^5\) なので十分高速に動作します。

実装のポイント

• 0-indexed と 1-indexed の変換: 管理番号は \(1\) から始まりますが、Pythonの配列は \(0\) から始まるため、A[b - 1] のようにインデックスを \(1\) ずらしてアクセスします。

• 高速な入力: \(N, M\) が最大 \(10^5\) と大きいため、sys.stdin.buffer.read() でまとめて読み込み、split() で分割する方法を使うと、input() を繰り返し呼ぶよりも高速です。

• 蔵書数・貸出冊数が最大 \(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
    A = [int(input_data[idx + i]) for i in range(N)]
    idx += N
    for _ in range(M):
        b = int(input_data[idx]); idx += 1
        c = int(input_data[idx]); idx += 1
        if A[b - 1] >= c:
            A[b - 1] -= c
    print(' '.join(map(str, A)))

main()

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