概要

\(M\) 人のアルバイトを、それぞれ異なる営業日に割り当て、売上見込みの合計を最大化する問題です。ただし、各アルバイトは一定のスキルレベル以下の営業日にしか出勤できず、1日に割り当てられるのは1人だけです。

考察

この問題では、各アルバイトをどの営業日に割り当てるかが重要になります。単純な貪欲法としては、売上見込みが最も高い営業日を順に選ぶという方法が考えられますが、それだとスキルレベルの制限を無視してしまうため、不適切です。

重要な観察は、「スキルレベルが低いアルバイトから順に、割り当て可能な営業日の中から最も売上見込みが高いものを選ぶ」という貪欲法が最適であることです。なぜなら、スキルレベルが低いアルバイトほど選べる営業日の候補が少なく、選択肢が限られているため、早めに最適な日を確保しておくべきだからです。

素朴な方法では、毎回割り当て可能な営業日を線形探索すると、全体で \(O(NM)\) となり、制約が大きいのでTLEしてしまいます。そこで、効率的に最大の売上を見つけるために、優先度付きキュー（ヒープ） を使うことで高速化します。

アルゴリズム

1. 営業日を必要スキルレベル \(H_i\) の昇順にソートします。
2. アルバイトもスキルレベル \(P_j\) の昇順にソートします。
3. スキルレベルの低いアルバイトから順に処理します。
4. そのアルバイトが働ける営業日（\(H_i \leq P_j\)）を、売上見込み \(S_i\) の降順で管理するヒープに追加します。
5. ヒープから最も売上見込みの高い日を選び、その売上を答えに加えます。
6. もし割り当て可能な営業日がなければ -1 を出力します。

具体例

例えば以下のような入力の場合：

N=3, M=2
H = [2, 1, 3]
S = [100, 200, 300]
P = [2, 3]

• ソート後の営業日：\((1, 200), (2, 100), (3, 300)\)
• アルバイトのスキル：\([2, 3]\)

最初のアルバイト（スキル2）は \((1,200)\) と \((2,100)\) から選べるので、売上200を選ぶ。
次のアルバイト（スキル3）は \((3,300)\) を選ぶ。
合計売上は \(200 + 300 = 500\) となります。

計算量

• 時間計算量: \(O(N \log N + M \log M + N \log N)\) → 全体で \(O((N + M) \log N)\)
• 空間計算量: \(O(N + M)\)

実装のポイント

• 営業日とアルバイトはそれぞれスキルレベルでソートすること。

• 売上見込みの最大値を効率良く取得するために、Pythonの heapq モジュールを使い、符号を反転させて最大ヒープを実現している。

• 各アルバイトに対して、自身が働ける営業日を前から順にヒープに追加していくことで、重複なく処理できる。

  ソースコード

import sys
from heapq import heappush, heappop

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    
    H = [0] * N
    S = [0] * N
    index = 2
    for i in range(N):
        H[i] = int(data[index])
        S[i] = int(data[index+1])
        index += 2
    
    P = list(map(int, data[index:index+M]))
    
    # 営業日を (H_i, S_i) のタプルで持つ
    days = [(H[i], S[i]) for i in range(N)]
    # H_i でソートしておく
    days.sort()
    
    # アルバイトもスキルレベルでソート
    P.sort()
    
    # 各アルバイトに対して、割り当て可能な営業日のうち売上見込みが最大のものを選ぶ
    # 売上見込みの最大値を効率的に管理するために、優先度付きキューを使う
    
    # 割り当て可能な営業日を管理するためのヒープ
    # ただし、売上見込みの最大値を取り出すために、-S_i をヒープに入れる
    heap = []
    
    total_profit = 0
    day_index = 0
    
    # スキルレベルが低いアルバイトから順に処理
    for p in P:
        # このアルバイトが割り当て可能な営業日をヒープに追加
        while day_index < N and days[day_index][0] <= p:
            heappush(heap, -days[day_index][1])
            day_index += 1
        
        # 売上見込みが最大のものを割り当てる
        if heap:
            max_profit = -heappop(heap)
            total_profit += max_profit
        else:
            # 割り当て可能な営業日がない場合
            print(-1)
            return
    
    print(total_profit)

if __name__ == "__main__":
    main()

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