概要

\(N\) 個の図書館におけるジャンルごとの蔵書を管理し、\(Q\) 件の貸出申請を時系列順に処理して、最終的な蔵書数と貸出失敗の総数を求めるシミュレーション問題です。

考察

この問題で求められている操作は、各貸出申請に対して「在庫があれば 1 冊減らす」「在庫がなければ失敗としてカウントする」という非常にシンプルなものです。

• シミュレーションの妥当性: 貸出申請の数は最大 \(2 \times 10^5\) 件、全図書館のジャンル数の合計は最大 \(10^5\) です。1 回の申請につき、該当する図書館の特定のジャンルの在庫を確認して更新する操作は \(O(1)\) で行えるため、全体でも \(O(\sum M_i + Q)\) の計算量で処理が可能です。これは制限時間内に十分間に合う計算量です。
• データ構造の選択: 「図書館番号」と「ジャンル番号」の 2 つの添字で在庫数にアクセスする必要があるため、2 次元配列（Python ではリストのリスト）で管理するのが自然です。
• 入出力の高速化: 入力データの数が最大で数十万件に及ぶため、input() を繰り返すと実行時間が長くなる可能性があります。sys.stdin.read().split() などを用いて一括で読み込む工夫が有効です。

アルゴリズム

1. データの読み込み: 全ての入力を数値のリストとして一括で取得します。
2. 蔵書データの初期化:
   • 各図書館の情報を順に読み取り、libraries[i][j] が「図書館 \(i\) のジャンル \(j\) の蔵書数」を表すような 2 次元リストを作成します。
   • このとき、問題文の図書館番号・ジャンル番号は 1 から始まる（1-indexed）ため、プログラム上の 0 から始まるインデックス（0-indexed）に合わせるよう調整します。
3. 貸出申請の処理:
   • \(Q\) 個の申請を順に処理します。
   • 図書館 \(v_k\)、ジャンル \(d_k\) の在庫が 1 以上なら、在庫を 1 減らします。
   • 在庫が 0 なら、失敗回数（failed_count）を 1 増やします。
4. 結果の出力:
   • 各図書館の最終的な在庫状況をスペース区切りで出力します。
   • 最後に、累積した失敗回数を出力します。

計算量

• 時間計算量: \(O(\sum M_i + Q)\)
  • 入力の読み込みに \(O(\sum M_i + Q)\)、貸出申請の処理に \(O(Q)\)、結果の出力に \(O(\sum M_i)\) かかります。
• 空間計算量: \(O(\sum M_i + Q)\)
  • 全ジャンルの蔵書数を保持するために \(O(\sum M_i)\)、入力データを保持するために \(O(\sum M_i + Q)\) のメモリを使用します。

実装のポイント

• 1-indexed と 0-indexed: 入力される \(v_k\) や \(d_k\) は 1 から始まります。配列のインデックスとして使う際は必ず 1 を引く必要があります。
• Python での高速な出力: print を何度も呼び出すのではなく、出力したい文字列をリストに溜めておき、"\n".join() で結合して一気に出力することで、実行時間を短縮できます。
• メモリ管理: sys.stdin.read().split() は全データをメモリに載せるため、非常に巨大な入力の場合は注意が必要ですが、今回の制約（合計 \(3 \times 10^5\) 個程度の整数）であれば問題ありません。”`python import sys

def solve(): # 標準入力からすべてのデータを読み込み、空白文字で分割してリストにする try: input_data = sys.stdin.read().split() except EOFError: return

if not input_data:
    return

tokens = list(map(int, input_data))

ptr = 0
# 図書館の数 N を取得
N = tokens[ptr]
ptr += 1

# 各図書館のジャンルごとの蔵書数を格納するリスト
libraries = [None] * N
for i in range(N):
    m_i = tokens[ptr]
    ptr += 1
    # スライスを使用して、図書館 i の各ジャンルの初期蔵書数を取得
    libraries[i] = tokens[ptr : ptr + m_i]
    ptr += m_i

# 貸出申請の件数 Q を取得
if ptr >= len(tokens):
    Q = 0
else:
    Q = tokens[ptr]
    ptr += 1

failed_count = 0
# 各貸出申請を順に処理
for _ in range(Q):
    v_k = tokens[ptr]
    d_k = tokens[ptr + 1]
    ptr += 2

    # 0-indexed に変換
    lib_idx = v_k - 1
    genre_idx = d_k - 1

    # 在庫確認と更新
    if libraries[lib_idx][genre_idx] > 0:
        libraries[lib_idx][genre_idx] -= 1
    else:
        failed_count += 1

# 出力結果の作成
output_results = []
for i in range(N):
    output_results.append(" ".join(map(str, libraries[i])))
output_results.append(str(failed_count))

# 一括出力
sys.stdout.write("\n".join(output_results) + "\n")

if name == ‘main’: solve()

## ソースコード

```python
import sys

def solve():
    # 標準入力からすべてのデータを読み込み、空白文字で分割してリストにする
    # sys.stdin.read().split() は、スペース、タブ、改行などのすべての空白文字を処理します。
    try:
        input_data = sys.stdin.read().split()
    except EOFError:
        return
    
    # 入力が空の場合は何もしない
    if not input_data:
        return
    
    # リストの全要素を整数に変換する
    # map(int, ...) は高速に変換を行うことができます。
    tokens = list(map(int, input_data))
    
    ptr = 0
    # 図書館の数 N を取得
    if ptr >= len(tokens):
        return
    N = tokens[ptr]
    ptr += 1
    
    # 各図書館のジャンルごとの蔵書数を格納するリスト
    # libraries[i] は図書館 (i+1) の各ジャンルの蔵書数のリストを保持します。
    libraries = [None] * N
    for i in range(N):
        # 図書館 i のジャンル数 M_i を取得
        m_i = tokens[ptr]
        ptr += 1
        # スライスを使用して、図書館 i の各ジャンルの初期蔵書数を取得する
        # スライスによって新しいリストが作成されるため、元の tokens は変更されず、
        # libraries[i] の値を個別に更新することができます。
        libraries[i] = tokens[ptr : ptr + m_i]
        ptr += m_i
        
    # 貸出申請の件数 Q を取得
    if ptr >= len(tokens):
        Q = 0
    else:
        Q = tokens[ptr]
        ptr += 1
    
    failed_count = 0
    # 各貸出申請を順に処理する
    for _ in range(Q):
        if ptr + 1 >= len(tokens):
            break
        v_k = tokens[ptr]
        d_k = tokens[ptr + 1]
        ptr += 2
        
        # 図書館番号 v_k とジャンル番号 d_k は 1-indexed なので、
        # リストのインデックスに合わせて 0-indexed に変換する
        lib_idx = v_k - 1
        genre_idx = d_k - 1
        
        # 在庫があるか確認し、あれば 1 冊減らし、なければ失敗回数をカウントする
        if libraries[lib_idx][genre_idx] > 0:
            libraries[lib_idx][genre_idx] -= 1
        else:
            failed_count += 1
            
    # 出力結果のリストを準備する
    output_results = []
    for i in range(N):
        # 各図書館の残り蔵書数をスペース区切りで連結
        output_results.append(" ".join(map(str, libraries[i])))
    
    # 貸出が失敗した合計回数を追加
    output_results.append(str(failed_count))
    
    # すべての結果を改行で連結して一括出力する
    sys.stdout.write("\n".join(output_results) + "\n")

if __name__ == '__main__':
    solve()

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