概要

図書館の貸出記録を順に処理し、各図書館の各ジャンルの残り蔵書数と貸出失敗回数を出力する問題です。

考察

問題は単純に各貸出申請を順番に処理するだけですが、以下の点に注意する必要があります： - 蔵書数が0の場合は貸出が失敗し、蔵書数は変化しない - 蔵書数が1以上の場合は貸出が成功し、蔵書数を1減らす - 入力サイズが大きい（最大20万件の貸出申請）ため、効率的な処理が必要

素朴なアプローチ（各貸出申請に対して直接蔵書数を更新）は、各操作が定数時間で処理できるため十分効率的です。特に、蔵書数の更新は配列の要素へのアクセスと減算だけで済むため、高速に処理できます。

アルゴリズム

1. 入力データを読み込み、各図書館の蔵書数を2次元配列で保持
2. 貸出申請を順次処理：
   • 対象図書館とジャンルの蔵書数をチェック
   • 蔵書数が0より大きければ1減らす
   • 蔵書数が0なら失敗カウントを増やす
3. 処理後の各図書館の蔵書数を出力
4. 失敗回数の合計を出力

計算量

• 時間計算量: \(O(Q + \sum_{i=1}^{N} M_i)\)
  • 入力読み込み: \(O(\sum_{i=1}^{N} M_i)\)
  • 貸出処理: \(O(Q)\)
  • 出力: \(O(\sum_{i=1}^{N} M_i)\)
• 空間計算量: \(O(\sum_{i=1}^{N} M_i)\)
  • 蔵書データを格納するためのメモリ

実装のポイント

• 配列のインデックスは0始まりなので、入力の図書館番号vから1を引き、ジャンル番号dから1を引いて正しいインデックスを計算

• 蔵書数が0かどうかのチェックを厳密に行う（負の数にならないように）

• 入力データを一度に読み込んで処理することで効率化

• 出力時にリストを文字列に変換する際はjoinメソッドを使用

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    
    index = 0
    N = int(data[index]); index += 1
    libraries = []
    total_books = 0
    
    for i in range(N):
        M_i = int(data[index]); index += 1
        books = list(map(int, data[index:index+M_i]))
        index += M_i
        libraries.append(books)
        total_books += M_i
        
    Q = int(data[index]); index += 1
    fail_count = 0
    
    for i in range(Q):
        v = int(data[index]); index += 1
        d = int(data[index]); index += 1
        library_index = v - 1
        genre_index = d - 1
        
        if libraries[library_index][genre_index] > 0:
            libraries[library_index][genre_index] -= 1
        else:
            fail_count += 1
            
    for books in libraries:
        print(" ".join(map(str, books)))
        
    print(fail_count)

if __name__ == "__main__":
    main()

---

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