概要

\(N\) 人のアルバイトと \(M\) 個の業務がある。各業務にはスキル値が十分なアルバイトを割り当て、満足度の合計を最大化する問題。

考察

この問題では、各業務にちょうど一人のアルバイトを割り当てなければならない。ただし、あるアルバイトが担当できるのは高々一つの業務であり、またそのアルバイトのスキル値 \(A_i\) が業務の要求スキル値 \(D_j\) 以上でなければならない（つまり、\(A_i - D_j \geq 0\)）。

重要な観察

• 業務をスキル値の高い順に処理することで、より多くの候補から選べるようになる。
• 各業務に対して、その要求スキル値を満たす中で最もスキルが高いアルバイトを選ぶのが最適である（貪欲法）。
• しかし、単純に「最もスキルが高い人」だけを使うと、後ろの業務で使える人がいなくなる可能性がある。

解決策：優先度付きキュー（ヒープ）の活用

• 各業務ごとに、その時点で担当可能なアルバイトの中から、最もスキル値が高い人を選ぶ。
• このとき、すでに見たことのあるスキル値の高いアルバイトを再利用するために、最大ヒープを用いる。
• 毎回全探索すると時間がかかるので、ヒープに候補を追加しながら取り出すことで効率よく処理する。

具体例

例えば以下のような入力を考える：

N=3, M=2
A = [5, 3, 4]
D = [4, 3]

1. 昇順に並べ替えておく：

   • A = [5, 4, 3]
   • D = [4, 3]

2. 業務の要求スキルが高い順に処理（D=[4,3]）：

   • D=4: A>=4 であるのは [5,4] → ヒープに入れる → 最大の5を選択
   • D=3: A>=3 であるのは残りの4と3 → ヒープから最大の4を選択

結果的に満足度は \((5-4)+(4-3)=2\)

アルゴリズム

1. アルバイトのスキル値リスト \(A\) と業務の要求スキル値リスト \(D\) をそれぞれ降順にソートする。
2. 要求スキルが高い業務から順に処理していく。
3. 各業務について：
   • まだ使われていないアルバイトの中で、現在の業務の要求スキル値以上のものをヒープに追加する。
   • ヒープが空であれば、割り当て不可なので -1 を出力して終了。
   • そうでなければ、ヒープから最もスキル値が高いアルバイトを取り出し、その業務を割り当てる。
   • 取り出したアルバイトによる満足度 \(A_i - D_j\) を加算する。
4. 全ての業務が割り当てられたら、得られた満足度の合計を出力する。

計算量

• 時間計算量: \(O(N \log N + M \log M + M \log N)\)
  （ソートが支配的。さらにヒープ操作が \(M\) 回行われ、それぞれ \(O(\log N)\)）
• 空間計算量: \(O(N)\)
  （ヒープに最大 \(N\) 要素格納）

実装のポイント

• Python の heapq は最小ヒープなので、最大ヒープとして使うには要素を符号反転させる必要がある。
• アルバイトと業務の両方を降順にソートすることで、必要な情報だけをヒープに詰め込める。
• 各業務に対して、条件を満たすアルバイトが存在しなければ即座に -1 を返すことで早期終了できる。

## ソースコード

```python
import heapq

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    A = list(map(int, data[2:2+N]))
    D = list(map(int, data[2+N:2+N+M]))
    
    # スキル値と要求スキル値を降順にソート
    A.sort(reverse=True)
    D.sort(reverse=True)
    
    # 最大ヒープ（Pythonでは最小ヒープなので、符号反転して利用）
    heap = []
    total_satisfaction = 0
    a_index = 0
    
    for d in D:
        # 現在の業務の要求スキル値 d に対して、A_i >= d となる i を探す
        while a_index < N and A[a_index] >= d:
            heapq.heappush(heap, -A[a_index])  # 最大ヒープとして使うために符号反転
            a_index += 1
        
        # ヒープが空なら、この業務を誰にも割り当てられない
        if not heap:
            print(-1)
            return
        
        # 満足度が最大になるようなアルバイトを選ぶ（貪欲法）
        max_a = -heapq.heappop(heap)
        total_satisfaction += max_a - d
    
    print(total_satisfaction)

if __name__ == "__main__":
    main()

---

この解説は qwen3-coder-480b によって生成されました。