概要

各座席エリアに定員が設定されたコンサートで、ファンが順番に予約を試み、定員内なら予約成功となります。予約成功した全ファンのチケット価格の合計を求める問題です。

考察

この問題のポイントは以下の通りです。

• ファンは順番に予約を試みます。先着順で、定員に達していなければ予約成功、達していれば予約失敗です。
• 各エリアごとに「あと何人予約できるか（残り座席数）」を管理すれば、各ファンの予約成否を判定できます。

具体例で考えてみましょう。

例えば、エリア1の価格が \(C_1 = 5000\)、定員が \(K_1 = 2\) のとき： - 1人目がエリア1を予約 → 残り1席 → 成功（+5000） - 2人目がエリア1を予約 → 残り0席 → 成功（+5000） - 3人目がエリア1を予約 → 残り0席で定員到達済み → 失敗

このように、残り座席数をカウントダウンしていくだけで判定できます。

素朴なアプローチとの比較：

この問題自体はシンプルなシミュレーションで解けるため、特別な工夫は不要です。ただし、Pythonでは入力が大量（最大 \(10^5\) 行以上）になる場合、input() を1行ずつ呼ぶと遅くなるため、sys.stdin.read() でまとめて読み込むことが重要です。

アルゴリズム

1. \(N\) 個のエリアについて、価格 \(C_i\) と定員（残り座席数） \(K_i\) を配列に格納する。
2. \(M\) 人のファンを順番に処理する：
   • ファン \(j\) が予約したいエリア \(P_j\) について、\(K[P_j] > 0\)（残席あり）なら：
     • \(K[P_j]\) を1減らす（座席を1つ消費）
     • 合計金額に \(C[P_j]\) を加算する
   • そうでなければ何もしない（予約失敗）
3. 最終的な合計金額を出力する。

計算量

• 時間計算量: \(O(N + M)\)
  • エリア情報の読み込みに \(O(N)\)、ファンの予約処理に \(O(M)\)（各ファンの処理は \(O(1)\)）
• 空間計算量: \(O(N)\)
  • 各エリアの価格と残り座席数を保持する配列

実装のポイント

• 高速な入力処理: Pythonでは sys.stdin.read() で全入力を一括読み込みし、split() で分割してインデックスで順にアクセスする方法が高速です。input() を \(M\) 回呼ぶよりも大幅に速くなります。

• 1-indexed の配列: エリア番号が \(1\) から \(N\) なので、配列を \(N+1\) のサイズで確保し、インデックス \(1\) から \(N\) を使うと、番号変換の手間がなくなります。

• 残り座席数の直接管理: 予約人数を数えて定員と比較する方法でも正しいですが、残り座席数をデクリメントしていく方がシンプルで効率的です。

  ソースコード

import sys

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    C = [0] * (N + 1)
    K = [0] * (N + 1)
    for i in range(1, N + 1):
        C[i] = int(input_data[idx]); idx += 1
        K[i] = int(input_data[idx]); idx += 1
    
    total = 0
    for j in range(M):
        p = int(input_data[idx]); idx += 1
        if K[p] > 0:
            K[p] -= 1
            total += C[p]
    
    print(total)

main()

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