概要

各ショップに会員枠（定員）があり、顧客が順番に申請してくる中で、定員に空きがあれば登録し、満員なら最も優先度が低い既存会員と比較して入れ替えるかどうかを判定する問題です。最終的な各ショップの会員数を求めます。

考察

重要な気づき

各ショップについて、常に「現在登録されている会員の中で最も優先度が低い人」を高速に取得できる必要があります。

例えば、ショップの定員が 2 で、優先度 3, 7 の会員が登録されている状態で優先度 5 の顧客が申請してきた場合： - 最も優先度が低い会員は優先度 3 の人 - 申請者の優先度 5 > 3 なので、優先度 3 の人を解除し、優先度 5 の人を登録 - 結果：ショップには優先度 5, 7 の会員が登録される

素朴なアプローチの問題

もし毎回ショップの全会員を走査して最小優先度を探すと、最悪 \(O(Q \times N)\) となり、\(N, Q\) が最大 \(2 \times 10^5\) の場合は間に合いません。

解決策

最小ヒープ（min-heap） を使えば、最小優先度の取得・入れ替えが \(O(\log N)\) で行えます。各ショップごとにヒープを管理すれば、全体として効率的に処理できます。

アルゴリズム

1. 各ショップに対して最小ヒープ（min-heap）を用意する。
2. \(Q\) 件の申請を順番に処理する。各申請 \((P_k, D_k)\) について：
   • 申請者の優先度 \(A_{P_k}\) を取得する。
   • ショップ \(D_k\) の現在の会員数が定員 \(C_{D_k}\) 未満なら、ヒープに優先度を追加し、会員数を +1 する。
   • 定員に達している場合、ヒープの先頭（最小優先度）と申請者の優先度を比較する。
     • 申請者の優先度の方が真に大きければ、heapreplace でヒープの最小値を申請者の優先度に置き換える（会員数は変わらない）。
     • そうでなければ、申請を却下する（何もしない）。
3. 全申請の処理後、各ショップの会員数を出力する。

heapreplace は「ヒープから最小値を取り出し、新しい値を挿入する」操作を 1 回の \(O(\log n)\) で行う関数です。

計算量

• 時間計算量: \(O(Q \log N)\)
  • 各申請でヒープ操作を最大 1 回行い、ヒープのサイズは最大 \(C_j \leq N\) なので、1 回あたり \(O(\log N)\)。
• 空間計算量: \(O(N + M + Q)\)
  • 各ショップのヒープに格納される要素の総数は最大 \(Q\)（各顧客は高々 1 回申請するため）。ショップ配列に \(O(M)\)。

実装のポイント

• Python の heapq モジュールは最小ヒープを提供するため、この問題の「最も優先度が低い会員を取得する」操作にそのまま使えます。

• heapq.heapreplace(heap, val) は pop と push を別々に行うより効率的です（ヒープの再構築が 1 回で済む）。

• 会員数は len(shops[j]) でも取得できますが、別途 shop_sizes 配列で管理することで余計なオーバーヘッドを避けています。

• sys.stdin.readline を使うことで入力の読み込みを高速化しています。大量の入力がある競技プログラミングでは重要なテクニックです。

  ソースコード

import heapq
import sys
input = sys.stdin.readline

def main():
    N, M, Q = map(int, input().split())
    A = list(map(int, input().split()))
    C = list(map(int, input().split()))
    
    # Min-heaps for each shop (store priorities)
    shops = [[] for _ in range(M)]
    shop_sizes = [0] * M
    
    for _ in range(Q):
        P, D = map(int, input().split())
        p_priority = A[P - 1]
        d_idx = D - 1
        cap = C[d_idx]
        
        if shop_sizes[d_idx] < cap:
            heapq.heappush(shops[d_idx], p_priority)
            shop_sizes[d_idx] += 1
        else:
            # Shop is full, compare with minimum priority member
            if shops[d_idx] and p_priority > shops[d_idx][0]:
                heapq.heapreplace(shops[d_idx], p_priority)
            # else: rejected
    
    print(' '.join(str(shop_sizes[j]) for j in range(M)))

main()

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