概要

\(N\) 人のアルバイトから \(M\) 人を選び、それぞれを \(M\) 個の業務に割り当てて、全員の「スキル値 \(-\) 要求スキル値」の合計を最大化する問題です。ただし、全員の満足度が \(0\) 以上（スキル値 \(\geq\) 要求スキル値）である必要があります。

考察

この問題を解くためのポイントは、「どの \(M\) 人を選ぶか」と「選んだ人をどう割り当てるか」の 2 点です。

1. 満足度の合計を式変形する

選ばれた \(M\) 人のスキル値を \(A'_{1}, A'_{2}, \dots, A'_{M}\) とし、割り当てられた業務の要求スキル値を \(D_{1}, D_{2}, \dots, D_{M}\) とします。このとき、合計満足度は以下のように表せます。 $\(\sum_{i=1}^{M} (A'_{i} - D_{i}) = \left( \sum_{i=1}^{M} A'_{i} \right) - \left( \sum_{i=1}^{M} D_{i} \right)\)\( ここで、業務の要求スキル値の総和 \)\sum D_i\( は、どのアルバイトを割り当てても一定です。したがって、**満足度を最大化するには、選ぶ \)M\( 人のスキル値の総和 \)\sum A’_i$ を最大化すればよい**ことが分かります。

スキル値の総和を最大にするには、単純にスキル値が高い順に \(M\) 人のアルバイトを選べばよいことになります。

2. 割り当てが可能か判定する

スキル値が高い上位 \(M\) 人を選んだとき、条件（全員の満足度が \(0\) 以上）を満たす割り当てが存在するかを確認する必要があります。 「最もスキルが高い人から順に、最も要求スキル値が高い業務から順に割り当てる」という貪欲法を考えます。 スキル値を降順にソートしたものを \(A_1, A_2, \dots, A_N\)、要求スキル値を降順にソートしたものを \(D_1, D_2, \dots, D_M\) とすると、以下の条件がすべて成り立てば、割り当てが可能と言えます。 - \(A_1 \geq D_1\) - \(A_2 \geq D_2\) - \(\dots\) - \(A_M \geq D_M\)

もし、ある \(i\) について \(A_i < D_i\) となってしまう場合、上位 \(M\) 人を使っても条件を満たせません。このとき、よりスキル値の低いアルバイトを混ぜても状況は悪化するだけなので、どのように \(M\) 人を選んでも割り当ては不可能と判断できます。

アルゴリズム

1. アルバイトのスキル値 \(A\) を降順（大きい順）にソートする。
2. 業務の要求スキル値 \(D\) を降順（大きい順）にソートする。
3. \(i = 1, \dots, M\) について、 \(A_i < D_i\) となる箇所が一つでもあるか確認する。
   • 存在する場合、条件を満たす割り当ては不可能なので -1 を出力して終了する。
4. すべての \(i\) で \(A_i \geq D_i\) であれば、\((\sum_{i=1}^{M} A_i) - (\sum_{j=1}^{M} D_j)\) を計算して出力する。

計算量

• 時間計算量: \(O(N \log N)\)
  • スキル値のソートに \(O(N \log N)\) 、要求スキル値のソートに \(O(M \log M)\) かかります。その後の判定と合計の計算は \(O(M)\) なので、全体ではソートが支配的になります。
• 空間計算量: \(O(N + M)\)
  • 入力された値を保持するための配列のサイズです。

実装のポイント

• \(N, M\) が最大 \(2 \times 10^5\) と大きいため、Python では sys.stdin.read().split() などを用いて高速に入力を読み込むのが無難です。

• 満足度の合計を計算する際、先に \(A\) の上位 \(M\) 個の和と \(D\) の全要素の和を求めてから引き算を行うと効率的です。

  ソースコード

import sys

def solve():
    # Reading all input from standard input
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: number of workers, M: number of tasks
    N = int(input_data[0])
    M = int(input_data[1])
    
    # A: Skill values of N workers
    # D: Requirement values of M tasks
    # Using list(map(int, ...)) for faster conversion from string to integer
    A = list(map(int, input_data[2:2+N]))
    D = list(map(int, input_data[2+N:2+N+M]))
    
    # To maximize the sum of satisfaction, we should try to use the M workers 
    # with the largest skill values. If a valid assignment exists for any 
    # set of M workers, it will also exist for the M workers with the highest skills.
    # A set of M workers with skills S_1 >= S_2 >= ... >= S_M can be matched 
    # to M tasks with requirements D_1 >= D_2 >= ... >= D_M if and only if 
    # S_i >= D_i for all i = 0, 1, ..., M-1.
    
    # Sort both workers' skill values and task requirements in descending order.
    A.sort(reverse=True)
    D.sort(reverse=True)
    
    # Check if the M largest skill values can satisfy the M task requirements.
    # If A[i] < D[i] for any i, no valid assignment exists for any set of M workers.
    for i in range(M):
        if A[i] < D[i]:
            print("-1")
            return
    
    # If a valid assignment exists, the satisfaction sum is (sum of skills) - (sum of requirements).
    # Since the requirements are fixed, maximizing the skill sum of the M workers 
    # maximizes the total satisfaction.
    max_satisfaction = sum(A[:M]) - sum(D)
    print(max_satisfaction)

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-thinking によって生成されました。