概要

\(M\) 人のアルバイト全員を \(N\) 日の営業日に割り当てられるか判定し、可能な場合は売上の最大値を求めるマッチング最適化問題です。

考察

重要な気づき

1. アルバイトのスキル制約: アルバイト \(j\) は \(H_i \leq P_j\) を満たす日にのみ割り当て可能です。つまり、スキルレベルが低いアルバイトほど、割り当てられる日の選択肢が少なくなります。

2. 貪欲法の適用: スキルレベルの低いアルバイトから順に処理すると、後から処理するアルバイトは「前のアルバイトが対応可能な日 + 追加の日」に対応できます。これにより、選択肢が狭いアルバイトを先に処理する戦略が有効です。

素朴なアプローチの問題点

全てのアルバイトと営業日の組み合わせを試す方法では、\(O(N \times M)\) や二部マッチングで \(O(NM)\) 以上の計算量がかかり、\(N, M \leq 2 \times 10^5\) では TLE になります。

解決策

ソート + 優先度付きキュー（ヒープ） を使った貪欲法で効率化します。

• アルバイトをスキルレベル昇順でソート
• 営業日を必要スキルレベル昇順でソート
• 各アルバイトを処理する際、対応可能な日を順次ヒープに追加し、売上最大の日を選ぶ

アルゴリズム

1. 前処理

   • アルバイトのスキルレベル \(P\) を昇順ソート
   • 営業日を必要スキルレベル \(H\) の昇順でソート

2. 貪欲な割り当て

   • 最大ヒープ（売上が大きい順に取り出せる）を用意
   • スキルレベルの低いアルバイトから順に処理:
     • 現在のアルバイトのスキル \(P_j\) 以下の必要スキルを持つ日をヒープに追加
     • ヒープから売上最大の日を取り出して割り当て
     • ヒープが空なら割り当て不可能（-1 を出力）

3. 結果出力

   • 全員割り当て成功なら売上合計を出力

具体例

\(P = [3, 5, 7]\)（ソート済）、営業日が \((H, S) = [(2, 100), (4, 200), (6, 150)]\)（\(H\) でソート済）の場合：

• アルバイト1（スキル3）: \(H \leq 3\) の日 → \((2, 100)\) をヒープに追加 → 売上100を選択
• アルバイト2（スキル5）: \(H \leq 5\) の日 → \((4, 200)\) を追加 → 売上200を選択
• アルバイト3（スキル7）: \(H \leq 7\) の日 → \((6, 150)\) を追加 → 売上150を選択
• 合計: \(100 + 200 + 150 = 450\)

計算量

• 時間計算量: \(O(N \log N + M \log M + (N + M) \log N)\)
  • ソート: \(O(N \log N + M \log M)\)
  • ヒープ操作: 各日は高々1回追加・1回削除されるので \(O(N \log N)\)
  • 全体として \(O((N + M) \log N)\)
• 空間計算量: \(O(N + M)\)（ソート用配列とヒープ）

実装のポイント

• Python の heapq は最小ヒープなので、売上を負値にして追加することで最大ヒープとして使用

• 営業日の追加処理を while ループで行い、ポインタ day_idx を進めることで各日を1回だけ処理

• アルバイトが対応可能な日がない場合（ヒープが空）は即座に -1 を出力して終了

  ソースコード

import heapq
from collections import defaultdict

def solve():
    N, M = map(int, input().split())
    
    days = []
    for i in range(N):
        H, S = map(int, input().split())
        days.append((H, S))
    
    P = list(map(int, input().split()))
    
    # アルバイトをスキルレベルでソート（昇順）
    P.sort()
    
    # 営業日を必要スキルレベルでソート（昇順）
    # (H, S, original_index)
    sorted_days = sorted(enumerate(days), key=lambda x: x[1][0])
    
    # 貪欲法：スキルレベルの低いアルバイトから順に処理
    # 各アルバイトに対して、そのアルバイトが対応可能な日の中から
    # まだ割り当てられていない日で売上が最大のものを選ぶ
    
    # 最大ヒープを使用（Pythonはmin-heapなので負値を使う）
    max_heap = []
    day_idx = 0
    total_profit = 0
    assigned_count = 0
    
    for skill in P:
        # このアルバイトが対応可能な日（H <= skill）をヒープに追加
        while day_idx < N and sorted_days[day_idx][1][0] <= skill:
            orig_idx, (H, S) = sorted_days[day_idx]
            heapq.heappush(max_heap, -S)  # 最大ヒープのため負値
            day_idx += 1
        
        # ヒープから最大売上の日を選ぶ
        if max_heap:
            total_profit += -heapq.heappop(max_heap)
            assigned_count += 1
        else:
            # このアルバイトを割り当てられる日がない
            print(-1)
            return
    
    if assigned_count == M:
        print(total_profit)
    else:
        print(-1)

solve()

---

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