概要

スタッフのスキル \(A_i\) とタスクの必要スキル \(B_j\) から、「\(A_i \ge B_j\) を満たすペア」をできるだけ多く作り、その個数 \(\times C\) が最大売上になります。

考察

売上は「完成した料理の数」\(\times C\) なので、結局は 割り当て可能なタスクの最大個数（最大マッチ数） を求めればよい問題です。

素朴に考えると、 - 各スタッフがどのタスクを担当できるかを全探索する（\(O(NM)\)） - あるいは二部マッチング（最大流）で解く

などが思いつきますが、制約が \(N,M \le 2\times 10^5\) なので \(O(NM)\) は当然間に合いませんし、最大流もこの規模では重すぎます。

ここで重要な観察は次です。

• タスクを「必要スキルが低い順」に見ると、低いタスクほど担当できるスタッフが多い（条件がゆるい）
  
• 逆に、必要スキルが高いタスクは担当できるスタッフが限られる（条件がきつい）

したがって、簡単なタスク（必要スキルが小さい）から順に、担当できる中で最もスキルが低いスタッフを割り当てる のが自然です。
こうすると「高スキルのスタッフを温存」でき、後の難しいタスクをこなせる可能性を最大化できます。

さらに、スタッフをスキル昇順、タスクを必要スキル昇順にソートして考えると、

• あるスタッフのスキルが、今見ている（最小の）タスクすら満たせないなら、そのスタッフは以降のタスク（必要スキルはさらに高い）も絶対にできない

ので、そのスタッフは捨てて次へ進むのが最適です。

例： - スタッフ \(A=[2,4,7]\) - タスク \(B=[3,5,6]\)

小さい順に見ていくと、 - \(2\) は \(3\) を満たせない → このスタッフはどれも無理なのでスキップ - \(4\) は \(3\) を満たす → マッチ（1個） - 次のタスク \(5\) に対し、\(7\) は満たす → マッチ（2個） 最大で2個作れます。

アルゴリズム

1. 配列 \(A\)（スタッフのスキル）と \(B\)（タスク必要スキル）を昇順ソートする。
2. 2つのポインタ \(i\)（スタッフ側）、\(j\)（タスク側）を用意する（どちらも最小から見る）。
3. 以下を繰り返す：
   • もし \(A[i] \ge B[j]\) なら、このスタッフでこのタスクをこなせるので割り当てる（マッチ数を \(+1\)、\(i,j\) を両方進める）。
   • そうでなければ（\(A[i] < B[j]\)）、このスタッフは現在の最小タスクすらできず、今後もできないのでスタッフだけ進める（\(i\) を進める）。
4. マッチ数を \(cnt\) とすると答えは \(cnt \times C\)。

この方法は「常に最小のタスクに対して、可能な限り最小のスタッフを割り当てる」貪欲で、将来の選択肢（難しいタスク）を潰しにくいため最大マッチ数が得られます。

計算量

• 時間計算量: ソートに \(O(N\log N + M\log M)\)、2ポインタ走査に \(O(N+M)\) なので全体で \(O(N\log N + M\log M)\)
• 空間計算量: 配列保持で \(O(N+M)\)

実装のポイント

• \(N,M\) が大きいので、入力は sys.stdin.buffer.read() のように高速に読むと安全です。

• マッチ数 \(cnt \le 2\times 10^5\)、\(C \le 10^9\) なので最大売上は \(2\times 10^{14}\) 程度ですが、Python の int なら問題なく扱えます。

• 2ポインタは「マッチしたら両方進める」「マッチしなければスタッフだけ進める」を徹底すると実装が簡潔になります。

  ソースコード

import sys

def main():
    it = iter(map(int, sys.stdin.buffer.read().split()))
    N = next(it)
    M = next(it)
    C = next(it)
    A = [next(it) for _ in range(N)]
    B = [next(it) for _ in range(M)]

    A.sort()
    B.sort()

    i = j = 0
    cnt = 0
    while i < N and j < M:
        if A[i] >= B[j]:
            cnt += 1
            i += 1
            j += 1
        else:
            i += 1

    print(cnt * C)

if __name__ == "__main__":
    main()

---

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