概要

\(N\) 人のアルバイトから \(M\) 人を選んで \(M\) 個の業務に1対1で割り当て、全員の満足度（スキル値 − 要求スキル値）が非負となるようにしつつ、満足度の合計を最大化する問題です。

考察

重要な気づき①：満足度の合計の分解

満足度の合計は次のように書けます：

\[\sum_{(i,j) \in \text{割り当て}} (A_i - D_j) = \sum_{\text{選ばれた } i} A_i - \sum_{j=1}^{M} D_j\]

ここで \(\sum D_j\) は割り当て方に依存しない定数です。したがって、満足度の合計を最大化するには、選ぶ \(M\) 人のスキル値の合計をできるだけ大きくすればよいことが分かります。つまり、スキル値の大きい上位 \(M\) 人を選ぶのが最善です。

重要な気づき②：上位 \(M\) 人で不可能なら、どの \(M\) 人でも不可能

上位 \(M\) 人で有効な割り当てが作れない場合、それより小さいスキル値のアルバイトに入れ替えても状況は悪化するだけなので、解は存在しません。

重要な気づき③：実行可能性の判定

選んだ \(M\) 人と \(M\) 個の業務をそれぞれ適切にペアリングして、全ペアで \(A_i \geq D_j\) とできるかを判定する必要があります。

これは古典的な貪欲法の結果として、以下が知られています：

選んだアルバイトのスキル値を昇順に並べたものを \(A'_1 \leq A'_2 \leq \cdots \leq A'_M\)、業務の要求スキル値を昇順に並べたものを \(D_1 \leq D_2 \leq \cdots \leq D_M\) としたとき、有効な割り当てが存在する ⟺ すべての \(k\) について \(A'_k \geq D_k\)

直感的には、「一番難しい業務は一番スキルの高い人に、二番目に難しい業務は二番目にスキルの高い人に…」と対応させるのが最も制約を満たしやすいということです。

具体例: \(N=4, M=3\), \(A = [10, 7, 5, 3]\), \(D = [2, 4, 6]\)

• 上位3人: \(A' = [5, 7, 10]\)（昇順）, \(D = [2, 4, 6]\)（昇順）
• \(5 \geq 2\), \(7 \geq 4\), \(10 \geq 6\) → すべて OK
• 満足度合計 \(= (10+7+5) - (2+4+6) = 22 - 12 = 10\)

アルゴリズム

1. \(A\) を降順にソート、\(D\) を昇順にソートする。
2. 上位 \(M\) 人（\(A[0], A[1], \ldots, A[M-1]\)）を選ぶ。
3. 実行可能性を判定する：各 \(i = 0, 1, \ldots, M-1\) について \(A[i] \geq D[M-1-i]\) を確認する。
   • \(A[0]\)（最大）と \(D[M-1]\)（最大）、\(A[1]\)（2番目）と \(D[M-2]\)（2番目）…というペアリング。
4. すべて満たせば、答えは \(\sum_{i=0}^{M-1} A[i] - \sum_{j=0}^{M-1} D[j]\)。満たせなければ \(-1\)。

計算量

• 時間計算量: \(O(N \log N + M \log M)\)（ソートが支配的）
• 空間計算量: \(O(N + M)\)

実装のポイント

• \(A\) を降順、\(D\) を昇順にソートしておくと、実行可能性の判定で A[i] と D[M-1-i] を比較するだけで済み、シンプルに書けます。

• スキル値・要求値が最大 \(10^9\)、人数が最大 \(2 \times 10^5\) なので、合計値は最大約 \(2 \times 10^{14}\) になります。Python では整数のオーバーフローを気にする必要はありませんが、C++ などでは long long を使う必要があります。

  ソースコード

import sys

def solve():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    A = [int(input_data[idx + i]) for i in range(N)]; idx += N
    D = [int(input_data[idx + i]) for i in range(M)]; idx += M
    
    A.sort(reverse=True)
    D.sort()
    
    # To maximize the total satisfaction sum(A_i - D_j), we want to maximize sum(A_i) - sum(D_j).
    # sum(D_j) is fixed, so we want to maximize sum(A_i) of the chosen M workers.
    # We should pick the top M skilled workers and assign them to tasks.
    # But we need each assigned worker to have A_i >= D_j for their assigned task.
    
    # Greedy: Sort A descending, sort D ascending.
    # Try to assign the top M workers to tasks. Pair the largest A with the smallest D (to maximize sum and satisfy constraints).
    # Actually, to maximize the sum of A_i, we want to use the top M workers.
    # Pair them: A sorted descending with D sorted ascending -> A[0] with D[0], A[1] with D[1], ...
    # Wait, that pairs the best worker with the easiest task. The satisfaction per pair is A[i]-D[i].
    # We need A[i] >= D[i] for all pairs.
    
    # But actually, to maximize sum(A_i) we want the top M workers. Then we need a valid assignment.
    # For the top M workers (sorted descending) and tasks (sorted ascending), 
    # the optimal pairing to check feasibility is: pair the k-th largest worker with the k-th largest task.
    # i.e., A[0] with D[M-1], A[1] with D[M-2], ..., A[M-1] with D[0].
    # Wait no. Let me think again.
    
    # We want to maximize sum of A values used. So greedily pick top M workers.
    # For feasibility, we need to check if there's a valid matching where each worker can handle their task.
    # With A sorted descending and D sorted ascending:
    # A valid matching exists iff for each i in 0..M-1: A[i] >= D[M-1-i]
    # (pair largest A with largest D, second largest with second largest, etc.)
    # Actually the condition for a valid matching to exist (by Hall's theorem / greedy matching):
    # Sort both A (the chosen subset) and D in ascending order. Then A[i] >= D[i] for all i.
    
    # So: take top M from A, sort them ascending. Sort D ascending. Check A[i] >= D[i] for all i.
    # Top M from A sorted descending: A[0] >= A[1] >= ... >= A[M-1]
    # In ascending: A[M-1] <= ... <= A[0]
    # D ascending: D[0] <= D[1] <= ... <= D[M-1]
    # Condition: A[M-1-i] >= D[i] for ascending pairing, i.e. for i in 0..M-1: A_asc[i] >= D[i]
    # which means A[M-1] >= D[0], A[M-2] >= D[1], ..., A[0] >= D[M-1]
    
    # If top M workers can handle it, great. If not, we need to consider swapping some workers.
    # But actually if the top M can't do it, can a different subset do it?
    # If A[k] < D[M-1-k] for some k, replacing A[k] with a smaller value won't help.
    # So if top M doesn't work, no valid assignment exists.
    
    # Check feasibility: pair A[i] (desc) with D[M-1-i] (asc), i.e. A[i] with D[M-1-i]
    feasible = True
    for i in range(M):
        if A[i] < D[M - 1 - i]:
            feasible = False
            break
    
    if not feasible:
        print(-1)
        return
    
    # Maximum satisfaction = sum of top M A values - sum of all D values
    total = sum(A[:M]) - sum(D)
    print(total)

solve()

---

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