概要

この問題は、複数の図書館における各ジャンルの本の在庫を管理しながら、時系列順に与えられる貸出申請を処理し、最終的な在庫と貸出失敗回数を求めるものです。

考察

まず、問題の入力には非常に大きな値が含まれることがあり（例えば \(Q\) が最大 \(2 \times 10^5\)）、効率的な入出力処理が必要です。Python標準の input() 関数では遅いため、sys.stdin.read を使うことで高速化しています。

各図書館のジャンルごとの蔵書数を二次元リストなどで管理し、貸出申請に対しては指定された図書館・ジャンルの在庫があるかを確認します。在庫があれば在庫を減らし、なければ失敗カウントを増やすだけです。

素朴な方法でも解けそうな問題ですが、入力の処理を怠るとTLE（時間制限超過）になります。また、インデックスが1-originで与えられているため、0-originに合わせて調整する必要があります。

アルゴリズム

1. 最初にすべての図書館とジャンルごとの初期在庫を読み込みます。
2. 各貸出申請について以下を繰り返します：
   • 指定された図書館 \(v_k\) のジャンル \(d_k\) の在庫を確認。
   • 在庫が1冊以上あれば在庫を1減らす。
   • 在庫が0であれば、失敗回数を1増やす。
3. 全ての申請を処理した後、各図書館の最終在庫と失敗回数を出力。

計算量

• 時間計算量: \(O\left(\sum_{i=1}^{N} M_i + Q\right)\)
  （初期在庫の読み込みと貸出申請の処理の合計）
• 空間計算量: \(O\left(\sum_{i=1}^{N} M_i\right)\)
  （各図書館のジャンルごとの在庫を保存するため）

実装のポイント

• 入力を高速に行うために sys.stdin.read を使用。
• 図書館とジャンルの番号が1オリジンなので、内部処理では0オリジンに変換する必要がある（-1する）。
• 貸出申請の処理は単純な条件分岐で行い、在庫が0未満にならないように注意。

## ソースコード

```python
import sys
input = sys.stdin.read

def main():
    data = input().split()
    idx = 0
    N = int(data[idx])
    idx += 1
    
    libraries = []
    for i in range(N):
        M = int(data[idx])
        idx += 1
        books = list(map(int, data[idx:idx+M]))
        idx += M
        libraries.append(books)
    
    Q = int(data[idx])
    idx += 1
    
    fail_count = 0
    for _ in range(Q):
        v = int(data[idx]) - 1
        d = int(data[idx+1]) - 1
        idx += 2
        if libraries[v][d] > 0:
            libraries[v][d] -= 1
        else:
            fail_count += 1
    
    for lib in libraries:
        print(' '.join(map(str, lib)))
    print(fail_count)

if __name__ == "__main__":
    main()

---

この解説は qwen3-coder-480b によって生成されました。