概要

\(M\) 個のショップに対して \(Q\) 件の入会申請を順番に処理し、最終的な各ショップの会員数を求める問題です。会員枠が満杯の場合、最も優先度が低い会員と申請者を入れ替えるというルールを効率的にシミュレーションする必要があります。

考察

この問題の肝は、会員枠が満杯のショップに対して申請が来た際、「現在そのショップにいる会員の中で最も優先度が低い人」をいかに素早く見つけ、入れ替えるかという点にあります。

素朴なアプローチ

各ショップの会員リストを配列などで保持し、申請が来るたびにリストをソートして最小値を探すとします。 - 1回の申請あたりの処理: 会員数 \(K\) に対して \(O(K \log K)\) - 全体の計算量: \(O(Q \times N \log N)\) \(N, Q\) が最大 \(2 \times 10^5\) であるため、この方法では実行時間制限に間に合いません。

効率的なアプローチ

「最小値の取得」と「要素の追加・削除」を高速に行えるデータ構造が必要です。これに最適なのが優先度付きキュー（ヒープ）です。 各ショップの状態を最小ヒープ（Min-Heap）で管理することで、以下の操作が効率化できます。 - 最も優先度が低い会員の確認: \(O(1)\) - 会員の追加・入れ替え: \(O(\log (\text{会員数}))\)

各顧客は一度しか申請を行わないため、ヒープに格納される要素の総数は最大でも \(Q\) 個であり、十分高速に処理可能です。

アルゴリズム

1. 各ショップ \(j\) に対応する空の最小ヒープ shops_heaps[j] を用意します。
2. \(Q\) 件の申請を順番に処理します。各申請 \((P_k, D_k)\) について：
   • ショップ \(D_k\) の現在の会員数（ヒープのサイズ）が会員枠 \(C_{D_k}\) 未満の場合：
     • 顧客 \(P_k\) の優先度 \(A_{P_k}\) をヒープに追加します。
   • 会員枠が満杯の場合：
     • ヒープの先頭要素（最小値）と \(A_{P_k}\) を比較します。
     • \(A_{P_k}\) の方が大きければ、ヒープの最小値を取り除き、\(A_{P_k}\) を追加します。
     • そうでなければ、何もしません（申請却下）。
3. すべての処理が終わった後、各ヒープのサイズを出力します。

計算量

• 時間計算量: \(O(Q \log N)\)
  • \(Q\) 件の各申請に対し、ヒープ操作（追加・入れ替え）を \(O(\log C_j)\) で行います。\(C_j \leq N\) なので、全体で \(O(Q \log N)\) となります。
• 空間計算量: \(O(N + M + Q)\)
  • 優先度 \(A\)、会員枠 \(C\)、および各ショップのヒープに合計で最大 \(Q\) 個の要素を保持するため、線形時間程度のメモリを使用します。

実装のポイント

• 高速な入出力: \(N, M, Q\) が大きいため、Pythonでは sys.stdin.read().split() や sys.stdout.write を使用して入出力を高速化するのが一般的です。

• heapq.heapreplace: 会員を入れ替える際、heappop してから heappush するよりも、heapreplace を使う方が効率的です。これは最小値の取り出しと新しい要素の挿入を一度に行う関数です。

• 0-indexedへの変換: 入力される顧客番号やショップ番号は 1-indexed（1から始まる）なので、リストのインデックスとして使う際は 1 を引いて 0-indexed に直す必要があります。

  ソースコード

import sys
import heapq

def solve():
    # 高速な入力読み込み: すべての入力を一度に読み込み、整数のリストに変換します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    it = iter(map(int, input_data))
    
    try:
        N = next(it)
        M = next(it)
        Q = next(it)
    except StopIteration:
        return
    
    # A[i] は顧客 i+1 の優先度を格納します
    A = [next(it) for _ in range(N)]
        
    # C[j] はショップ j+1 の会員枠を格納します
    C = [next(it) for _ in range(M)]
        
    # 各ショップの現在の会員の優先度を最小ヒープで管理します
    # これにより、最も優先度が低い会員を O(log(会員枠)) で取得・更新できます
    shops_heaps = [[] for _ in range(M)]
    
    # Q 件の申請を順番に処理します
    for _ in range(Q):
        try:
            p_val = next(it)
            d_val = next(it)
        except StopIteration:
            break
            
        # 1-indexed から 0-indexed に変換
        p_idx = p_val - 1
        d_idx = d_val - 1
        
        priority = A[p_idx]
        capacity = C[d_idx]
        heap = shops_heaps[d_idx]
        
        if len(heap) < capacity:
            # 会員枠に空きがある場合は、そのまま登録されます
            heapq.heappush(heap, priority)
        elif priority > heap[0]:
            # 会員枠が満杯の場合、最も優先度が低い会員（heap[0]）と比較します
            # 申請者の優先度が真に大きければ、入れ替えを行います
            heapq.heapreplace(heap, priority)
        # それ以外の場合、申請は却下されます
            
    # 各ショップの最終的な会員数を取得します
    ans = [len(h) for h in shops_heaps]
    
    # 結果をスペース区切りで出力します
    sys.stdout.write(" ".join(map(str, ans)) + "\n")

if __name__ == '__main__':
    solve()

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