概要

この問題は、複数の顧客がショップへの会員登録を申請する際に、各ショップの会員枠と顧客の優先度に基づいて動的に登録・解除を行うシステムをシミュレーションし、最終的な各ショップの会員数を求める問題です。

考察

問題の核となるのは、各ショップで現在登録されている会員の中で最も優先度が低い会員を効率的に管理することです。申請が来るたびに、ショップの現在の会員数が会員枠に達している場合、最小優先度の会員と申請者の優先度を比較する必要があります。

素朴なアプローチとして、各ショップの会員リストを配列で保持し、毎回最小優先度を線形探索で探す方法が考えられますが、Q件の申請それぞれで最大N人の会員を調べることになるため、最悪計算量がO(QN)となり、制約条件（N, Q ≤ 2×10^5）では間に合いません。

そのため、各ショップで最小の優先度を高速に取得できるデータ構造として、最小ヒープ（優先度キュー）を使用します。ただし、ヒープから削除された要素を遅延的に処理する必要があります。

アルゴリズム

1. データ構造の準備:

   • shop_members[j]: ショップjに現在登録されている顧客IDの集合（存在確認用）
   • shop_heap[j]: ショップjの会員を（優先度, 顧客ID）で格納する最小ヒープ
   • customer_shop[i]: 顧客iが現在登録されているショップID（0は未登録）

2. 申請処理:

   • 顧客が既に別のショップに登録されている場合、元のショップから削除（集合から削除、ヒープは遅延削除）
   • 申請先ショップの会員数が会員枠未満の場合:
     • 顧客を新規登録（集合とヒープに追加）
   • 会員枠が満杯の場合:
     • ヒープの先頭から、有効な会員（集合に存在する）が見つかるまでポップ（遅延削除）
     • 有効な最小優先度会員と申請者を比較:

          - 申請者の優先度が大きい場合: 最小優先度会員を削除し、申請者を登録
          - そうでない場合: 申請を却下
       

3. 結果出力:

   • 全処理後、各ショップのshop_membersのサイズを出力

計算量

• 時間計算量: \(O(Q \log N)\)
  • 各申請処理でヒープ操作（push/pop）が定数回発生し、各操作は\(O(\log N)\)
  • 遅延削除による追加コストは償却定数時間
• 空間計算量: \(O(N + M)\)
  • 各データ構造が最大N人の顧客とM店舗分の情報を保持

実装のポイント

• 遅延削除の処理: ヒープから直接要素を削除する代わりに、有効な要素かどうかをshop_members集合で管理し、ヒープ操作時に有効でない要素をスキップする

• 状態の一貫性維持: 顧客の所属ショップ情報(customer_shop)、ショップの会員集合(shop_members)、ヒープ(shop_heap)の3つを常に同期させる

• 効率性: 集合による存在確認は\(O(1)\)で行え、ヒープ操作は\(O(\log N)\)であるため、全体として効率的な処理が可能

  ソースコード

import sys
import heapq

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    
    it = iter(data)
    N = int(next(it)); M = int(next(it)); Q = int(next(it))
    A = [0] * (N+1)
    for i in range(1, N+1):
        A[i] = int(next(it))
    
    C = [0] * (M+1)
    for j in range(1, M+1):
        C[j] = int(next(it))
    
    # 各ショップの現在の会員を管理: 最小ヒープ（優先度が低い順）と、会員の集合（所属ショップを追跡するため）
    shop_members = [set() for _ in range(M+1)]
    shop_heap = [[] for _ in range(M+1)]  # 最小ヒープ（優先度、顧客ID）を格納
    
    # 各顧客が現在所属しているショップ（0は未所属）
    customer_shop = [0] * (N+1)
    
    for _ in range(Q):
        p = int(next(it)); d = int(next(it))
        current_shop = customer_shop[p]
        if current_shop == d:
            continue
            
        # 現在のショップから削除（もし所属していれば）
        if current_shop != 0:
            shop_members[current_shop].discard(p)
            # ヒープからは削除できないので、遅延削除を行う
        
        # 新しいショップに登録を試みる
        target_shop = d
        if len(shop_members[target_shop]) < C[target_shop]:
            # 空きがあるので登録
            customer_shop[p] = target_shop
            shop_members[target_shop].add(p)
            heapq.heappush(shop_heap[target_shop], (A[p], p))
        else:
            # 空きがないので、最小優先度と比較
            while shop_heap[target_shop]:
                min_priority, min_customer = shop_heap[target_shop][0]
                if min_customer not in shop_members[target_shop]:
                    # 遅延削除：ヒープの先頭が実際には存在しない会員ならpop
                    heapq.heappop(shop_heap[target_shop])
                    continue
                break
            else:
                # ヒープが空（実際には会員枠いっぱいだがヒープに有効な要素がない）ということはないはず
                continue
                
            if A[p] > min_priority:
                # 入れ替え
                removed_customer = min_customer
                heapq.heappop(shop_heap[target_shop])
                shop_members[target_shop].remove(removed_customer)
                customer_shop[removed_customer] = 0
                
                customer_shop[p] = target_shop
                shop_members[target_shop].add(p)
                heapq.heappush(shop_heap[target_shop], (A[p], p))
            else:
                # 却下
                customer_shop[p] = 0
    
    # 各ショップの会員数を計算
    result = []
    for j in range(1, M+1):
        result.append(str(len(shop_members[j])))
    
    print(" ".join(result))

if __name__ == "__main__":
    main()

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