概要

図書館の蔵書管理システムをシミュレートする問題です。各本の初期蔵書数と貸出申請を順に処理し、最終的な蔵書数を求めます。

考察

この問題は、与えられた貸出申請を順番に処理していく単純なシミュレーション問題です。重要な点は、各申請に対して現在の蔵書数が要求冊数以上ある場合のみ貸出を実行し、蔵書数を減らすことです。蔵書数が不足している場合は何も変更しません。

素朴なアプローチとして、各貸出申請に対して直接配列の要素を更新する方法が考えられます。この方法は直感的で理解しやすく、制約条件内で十分に効率的です。

アルゴリズム

1. 初期蔵書数を格納する配列 A を読み込む
2. M件の貸出申請を順に処理する
3. 各申請について:
   • 対象の本の管理番号 b から配列のインデックスを計算 (b-1)
   • 現在の蔵書数 A[b-1] が要求冊数 c 以上かチェック
   • 条件を満たす場合のみ、蔵書数から c を減算する
4. すべての処理後に最終的な蔵書数を出力する

計算量

• 時間計算量: \(O(M)\)
  • M件の貸出申請をそれぞれ定数時間で処理するため
• 空間計算量: \(O(N)\)
  • 蔵書数を格納する配列のサイズがNであるため

実装のポイント

• 管理番号は1-indexedですが、配列は0-indexedなので、インデックス計算に注意が必要です (b-1)

• 各申請の処理は単純な比較と減算のみで、条件分岐が重要です

• 入力データの読み込みは一度にまとめて行うことで効率化しています

• 出力時には数値リストを文字列に変換してスペース区切りで出力します

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    m = int(data[1])
    A = list(map(int, data[2:2+n]))
    operations = []
    index = 2 + n
    for i in range(m):
        b = int(data[index])
        c = int(data[index+1])
        index += 2
        operations.append((b, c))
    
    for b, c in operations:
        idx = b - 1
        if A[idx] >= c:
            A[idx] -= c
    
    print(" ".join(map(str, A)))

if __name__ == "__main__":
    main()

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