概要

各座席エリアの残り定員を管理しながら、ファンの希望エリアを順に処理して「予約できた場合だけ価格を加算する」シミュレーションを行う問題です。

考察

• ファン \(j\) はエリア \(P_j\) を希望し、そのエリアの残り定員 \(K_{P_j}\) が 1 以上なら予約成功、0 なら失敗です。
• つまり必要なのは、各エリアについて「今あと何席残っているか」を覚えておき、希望が来るたびに
  • 残りがあれば \(K\) を 1 減らして価格 \(C\) を足す
  • 残りがなければ何もしない
    という処理をするだけです。

素朴に「各エリアに何人申し込んだか」を後から数えて \(\min(\text{申込数}, K_i)\) を計算する方法も可能ですが、結局は集計が必要であり、オンライン（順番通り）に処理しても結果は同じです。
制約が \(N, M \le 10^5\) なので、各ファンの処理を \(O(1)\) で行う必要があります（例えば毎回別のデータ構造を探索するような処理を入れると遅くなります）。

例： - エリア1: \(C_1=100, K_1=2\) - エリア2: \(C_2=200, K_2=1\) - 希望: \([1,2,1,2]\) - 1 → 成功（残り1）合計100 - 2 → 成功（残り0）合計300 - 1 → 成功（残り0）合計400 - 2 → 失敗（残り0）合計400

アルゴリズム

1. 配列 C[i] にエリア \(i\) の価格、配列 K[i] にエリア \(i\) の残り定員を保持する。
2. 合計 total = 0 を用意する。
3. 各ファンの希望エリア \(p\) について以下を行う：
   • もし K[p] > 0 なら
     • K[p] -= 1（1席予約で減る）
     • total += C[p]（価格を加算）
   • そうでなければ何もしない（満席で予約不可）
4. total を出力する。

計算量

• 時間計算量: \(O(N + M)\)（エリア情報の読み込み \(N\) 回 + ファン処理 \(M\) 回、各回 \(O(1)\)）
• 空間計算量: \(O(N)\)（価格と残り定員の配列）

実装のポイント

• 入力サイズが大きいので、Python では sys.stdin.buffer.read() でまとめて読み取り、split() して整数化すると高速です。

• 入力のエリア番号 \(P_j\) は \(1\) 始まりなので、配列アクセス用に p = P_j - 1 として \(0\) 始まりに直しています。

• 合計は最大で \(M \cdot 10^4 \le 10^9\) 程度ですが、Python の int は十分大きいのでオーバーフローは気にしなくてよいです。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    M = next(it)

    C = [0] * N
    K = [0] * N
    for i in range(N):
        C[i] = next(it)
        K[i] = next(it)

    total = 0
    for _ in range(M):
        p = next(it) - 1
        if K[p] > 0:
            K[p] -= 1
            total += C[p]

    sys.stdout.write(str(total))

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。