概要

\(N\) 館の図書館にそれぞれ複数ジャンルの蔵書があり、\(Q\) 件の貸出申請を順に処理して、最終的な蔵書数と貸出失敗回数を求めるシミュレーション問題です。

考察

この問題は特別なアルゴリズムを必要とせず、問題文の通りに忠実にシミュレーションすれば解けます。

重要な気づき

• 各貸出申請は「指定された図書館・ジャンルの蔵書を1冊減らす」操作です。
• ただし蔵書数が \(0\) のときは何もせず、代わりに失敗回数を \(1\) 増やします。
• 申請は時系列順に処理する必要があるため、まとめて計算するのではなく1件ずつ順番に処理します。

素朴なアプローチで十分か？

\(Q\) 件の申請をそれぞれ \(O(1)\) で処理できます。各申請に対して行う操作は「配列の特定の要素を参照し、条件に応じて1を引く」だけなので、全体で \(O(Q)\) です。\(Q \leq 2 \times 10^5\) なので十分高速です。

具体例で確認してみましょう。図書館1にジャンル1の本が3冊あるとき：

アルゴリズム

1. 入力読み込み: \(N\) 館分の蔵書データを二次元配列 libraries に格納する。
2. 貸出処理: \(Q\) 件の申請を順に処理する。
   • 図書館 \(v_k\)、ジャンル \(d_k\) の蔵書数が \(0\) より大きければ、蔵書数を \(1\) 減らす。
   • そうでなければ（蔵書数が \(0\)）、失敗カウント fail_count を \(1\) 増やす。
3. 出力: 各図書館の最終蔵書数を1行ずつ出力し、最後に失敗回数を出力する。

計算量

• 時間計算量: \(O\left(\sum_{i=1}^{N} M_i + Q\right)\)
  • 蔵書データの読み込みに \(O\left(\sum M_i\right)\)、貸出処理に \(O(Q)\)
• 空間計算量: \(O\left(\sum_{i=1}^{N} M_i\right)\)
  • 蔵書データを格納する配列の分

実装のポイント

• 0-indexed への変換: 問題文では図書館番号・ジャンル番号が \(1\) から始まるが、Pythonの配列は \(0\) から始まるため、v -= 1、d -= 1 として変換する。

• 高速な入力: \(Q\) が最大 \(2 \times 10^5\) あるため、sys.stdin.readline を使って入力を高速化している。標準の input() だとPythonでは遅くなる場合がある。

• 出力のまとめ書き: 各行を個別に print するのではなく、リストに溜めて最後に sys.stdout.write で一括出力することで、I/Oのオーバーヘッドを削減している。

  ソースコード

import sys
input = sys.stdin.readline

def main():
    N = int(input())
    libraries = []
    for i in range(N):
        line = list(map(int, input().split()))
        M_i = line[0]
        S = line[1:M_i+1]
        libraries.append(S)
    
    Q = int(input())
    fail_count = 0
    
    for _ in range(Q):
        v, d = map(int, input().split())
        v -= 1  # 0-indexed
        d -= 1  # 0-indexed
        if libraries[v][d] > 0:
            libraries[v][d] -= 1
        else:
            fail_count += 1
    
    out = []
    for i in range(N):
        out.append(' '.join(map(str, libraries[i])))
    out.append(str(fail_count))
    sys.stdout.write('\n'.join(out) + '\n')

main()

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