概要

各座席エリアの価格と定員、ファンが予約しようとするエリア情報から、実際に予約できたファンのチケット価格の合計を求める問題です。

考察

問題の本質は、各エリアの残り座席数を管理しながら、ファンの予約要求を順次処理することです。各エリアは独立しており、あるエリアが満席でも他のエリアには影響しません。素朴なアプローチでは、各エリアの残り座席数を配列で管理し、ファンが来るたびに対応するエリアの残り座席数を確認して処理します。制約条件が \(N, M \leq 10^5\) と大きいため、各処理を定数時間で行う必要があります。

アルゴリズム

1. 各エリアの情報（価格 \(C_i\) と定員 \(K_i\)）を読み込む
2. 各エリアの残り座席数を管理する配列 remaining を初期化（初期値は各エリアの定員 \(K_i\)）
3. 各ファンの予約要求を順に処理：
   • 要求されたエリア \(P_j\) のインデックスを計算（\(P_j - 1\)）
   • 対応するエリアの残り座席数が0より大きければ：
     • 残り座席数を1減らす
     • 合計金額にそのエリアの価格 \(C_i\) を加算する
4. 最終的な合計金額を出力する

計算量

• 時間計算量: \(O(M)\)
  • 各ファンの予約処理は定数時間で行えるため、\(M\) 人のファンを処理するのに \(O(M)\) 時間
• 空間計算量: \(O(N)\)
  • エリア情報と残り座席数を格納するために \(O(N)\) のメモリを使用

実装のポイント

• エリア番号は1-indexedで与えられるため、配列アクセス時には0-indexedに変換する必要がある

• 入力データが大きいため、sys.stdin.read() で一括読み込みして処理効率を向上させる

• 残り座席数の管理には単純な配列を使用し、各エリアへのアクセスを定数時間で行う

• 条件分岐は「残り座席数 > 0」のみで十分（負の値になる心配がない）

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        print(0)
        return
        
    it = iter(data)
    N = int(next(it))
    M = int(next(it))
    
    areas = []
    for _ in range(N):
        c = int(next(it))
        k = int(next(it))
        areas.append((c, k))
    
    bookings = []
    for _ in range(M):
        p = int(next(it))
        bookings.append(p)
    
    remaining = [k for _, k in areas]
    total_revenue = 0
    
    for p in bookings:
        idx = p - 1
        if remaining[idx] > 0:
            remaining[idx] -= 1
            total_revenue += areas[idx][0]
    
    print(total_revenue)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。