概要

必要スキル \(H_i\) と売上 \(S_i\) を持つ \(N\) 日から、各アルバイトのスキル \(P_j\) で出勤可能な日（\(H_i \le P_j\)）に 全員を重複なく割り当てられるかを判定し、可能なら 売上合計を最大化します。

考察

各アルバイトは「自分のスキル以下の必要スキルの日なら出勤できる」ので、アルバイト \(j\) は条件 \(H_i \le P_j\) を満たす日だけ選べます。また、1日につき1人までです。

重要な気づき

• 「割り当て可能かどうか」と「最大利益」を同時に考える必要があります。
• アルバイトのスキルが低い人ほど選べる日が少ないため、スキルの低い順に処理するのが自然です。
• あるアルバイト \(p\) を処理するとき、その時点で割り当て可能な日（\(H_i \le p\)）の中から 売上 \(S_i\) が最大のものを選ぶのが得です。

素朴な方法が難しい理由

• 全ての割り当てを探索すると組合せ爆発します（最大で \(N\) から \(M\) を選んで並べるような規模）。
• 二部マッチングをそのまま組むと、辺が「\(H_i \le P_j\)」で非常に多くなりうるため（最悪 \(NM\)）、制約 \(2 \times 10^5\) では現実的ではありません。

どう解決するか

「スキル順に見て、その時点で可能な日の中から最大売上を選ぶ」という貪欲を、効率よく実装します。 - 「その時点で可能な日」の集合を管理するために 優先度付きキュー（ヒープ） を使います。

アルゴリズム

1. 営業日を \((H_i, S_i)\) のペアとして用意し、必要スキル \(H_i\) の昇順にソートする。
2. アルバイトのスキル \(P_j\) も昇順にソートする。
3. 小さいスキルのアルバイトから順に処理する：
   • そのアルバイトのスキルを \(p\) とする。
   • まだ見ていない営業日のうち、\(H_i \le p\) を満たすものをすべてヒープに追加する（売上 \(S_i\) を入れる）。
   • ヒープが空なら、このアルバイトが入れる日がもう無いので 割り当て不可能（-1）。
   • ヒープから最大の \(S_i\) を取り出し、その日をこのアルバイトに割り当て、合計に加える。
4. 全アルバイトを処理できたら合計売上を出力する。

なぜこの貪欲が正しいか（直感）

スキルの低いアルバイトは選択肢が少ないため、後回しにすると詰みやすいです。
一方、あるスキル \(p\) の時点で選べる日（\(H_i \le p\)）は、将来（より高スキルのアルバイト）でも必ず選べます。
よって「今選べる中で一番売上が大きい日を今取る」ことで、将来の選択肢を不必要に狭めず、合計売上を最大化できます。

（簡単な例） - 日：\((H,S)=(1,10),(2,100)\) - アルバイト：\(P=(1,2)\)
\(P=1\) のとき選べるのは \(H=1\) の日だけなのでそれを取る（10）。
次に \(P=2\) は残った \(H=2\) の日（100）を取れる。合計110が最大です。

計算量

• 時間計算量: ソートに \(O(N\log N + M\log M)\)、各日を1回pushし各アルバイトで1回popするのでヒープ操作が \(O((N+M)\log N)\)。まとめて \(O((N+M)\log N)\)。
• 空間計算量: 営業日配列とヒープで最大 \(O(N)\)。

実装のポイント

• Python の heapq は最小ヒープなので、最大値を取りたい場合は \(-S_i\) を入れて取り出すときに符号を戻します。

• 営業日側は \(H_i\) の昇順に並べ、ポインタ idx を進めながら「\(H_i \le p\) になった日」をヒープに追加していくと、全体を1回ずつしか走査しません。

• 各アルバイトでヒープが空になった瞬間に -1 を出して終了すれば、判定も最大化も同時に行えます。

  ソースコード

import sys
import heapq

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    M = next(it)

    days = []
    for _ in range(N):
        h = next(it)
        s = next(it)
        days.append((h, s))
    days.sort()

    P = [next(it) for _ in range(M)]
    P.sort()

    heap = []
    idx = 0
    total = 0

    for p in P:
        while idx < N and days[idx][0] <= p:
            heapq.heappush(heap, -days[idx][1])
            idx += 1
        if not heap:
            print(-1)
            return
        total += -heapq.heappop(heap)

    print(total)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。