PythonでK人の労働者を雇うための最小コストを求めるプログラム

問題の概要

労働者ごとの能力値を格納した配列 quality と、それぞれの最低賃金の期待値を格納した配列 wage、そして雇用したい人数 K が与えられます。i 番目の労働者の能力値は quality[i]、最低賃金の期待値は wage[i] です。

K 人の労働者で賃金グループを結成する際には、次の2つのルールを守る必要があります。

• グループ内の各労働者への支払額は、グループ内の他のメンバーと比較した能力値(quality)の比率に応じて決まること。
• グループ内のすべての労働者が、少なくとも自分の最低賃金の期待値以上を受け取れること。

これらの条件を満たす賃金グループを結成するために必要な最小金額を求めます。

入出力例

たとえば、quality = [10, 22, 5]、wage = [70, 52, 30]、K = 2 が入力された場合、出力は 105.000 になります。1人目の労働者に 70 を支払い、3人目の労働者に 35 を支払うことで、両方のルールを同時に満たせるためです。

解法の考え方

この問題の鍵となるのは、支払総額が「グループ内で最も高い w/q 比率 × グループ全体の能力値の合計」で表されるという点です。この性質を利用して、以下の手順で解きます。

• 各労働者について「w/q(最低賃金期待値 ÷ 能力値)」を計算し、この値と能力値 q のペアをリスト qr に格納して昇順にソートします。比率が小さいほど、単位能力あたりのコストが安い労働者です。
• 候補管理用のヒープ cand と、能力値の合計 csum を用意します。
• i を 0 から K-1 までループし、ヒープ cand に -qr[i][1](能力値の符号を反転)を挿入しながら、csum に qr[i][1] を加算します。
• ans を csum × qr[K-1][0] で初期化します。
• idx を K から quality のサイズまでループし、ヒープ cand に -qr[idx][1] を挿入した後、csum に qr[idx][1] とヒープの先頭要素(= 現在の候補の中で最大の能力値)を加算して取り除きます。これにより、常に「能力値の合計が最小になる K 人」が候補として維持されます。
• ans を ans と csum × qr[idx][0] の最小値で更新し、最後に ans を返します。

最大ヒープを使って毎回最も能力値の大きい労働者を除外することで、各ステップでの候補選択を効率的に行えます。

実装例

以下のPythonコードで実際の動作を確認できます。

import heapq

def solve(quality, wage, K):
    # 時給比(w/q)と能力値のペアを作成してソート
    qr = []
    for q, w in zip(quality, wage):
        qr.append([w / q, q])
    qr.sort()

    # 最初のK人を候補として登録
    cand, csum = [], 0
    for i in range(K):
        heapq.heappush(cand, -qr[i][1])
        csum += qr[i][1]
    ans = csum * qr[K - 1][0]

    # 残りの労働者を順に検討し、より低コストな組み合わせを探索
    for idx in range(K, len(quality)):
        heapq.heappush(cand, -qr[idx][1])
        csum += qr[idx][1] + heapq.heappop(cand)
        ans = min(ans, csum * qr[idx][0])
    return ans

quality = [10, 22, 5]
wage = [70, 52, 30]
K = 2
print(solve(quality, wage, K))

入力

[10,22,5], [70,52,30], 2

出力

105

計算量

時間計算量は O(n log n)、空間計算量は O(n) です(n は労働者の人数)。ソートが支配的なコストとなり、以降のヒープ操作は全体で O(n log K) に収まります。