概要

スタッフのスキルレベルとタスクの必要スキルレベルをマッチングさせ、最大で何個のタスクを完了できるかを求める問題です。完了したタスク数に単価 \(C\) を掛けたものが答えになります。

考察

問題の本質を見抜く

この問題は、スタッフとタスクの「最大マッチング」を求める問題です。スタッフ \(i\) がタスク \(j\) を担当できる条件は \(A_i \geq B_j\)（スキルレベルが必要スキルレベル以上）です。

素朴なアプローチの問題点

全てのスタッフとタスクの組み合わせを試すと、\(O(N \times M)\) 通りの割り当てを考える必要があります。さらに最適な割り当てを求めるには二部マッチングのアルゴリズムが必要で、これは \(O(NM)\) 程度の計算量がかかります。\(N, M\) が最大 \(2 \times 10^5\) なので、この方法では間に合いません。

重要な気づき：貪欲法が使える

この問題には特殊な構造があります。スキルレベルと必要スキルレベルは「大小関係」だけで決まるため、ソートして貪欲に割り当てることで最適解が得られます。

直感的な説明： - スキルが高いスタッフは、どのタスクでも担当できる可能性が高い - 必要スキルが高いタスクは、担当できるスタッフが限られる - よって、スキルが高いスタッフには、必要スキルが高いタスクを優先的に割り当てるべき

具体例で確認

スタッフのスキル: \([5, 3, 8]\) → ソート後: \([8, 5, 3]\)
タスクの必要スキル: \([4, 7, 2]\) → ソート後: \([7, 4, 2]\)

1. スタッフ(スキル8) とタスク(必要7) → \(8 \geq 7\) なのでマッチング成功
2. スタッフ(スキル5) とタスク(必要4) → \(5 \geq 4\) なのでマッチング成功
3. スタッフ(スキル3) とタスク(必要2) → \(3 \geq 2\) なのでマッチング成功

結果：3個のタスクが完了

アルゴリズム

1. スタッフのスキルレベル配列 \(A\) を降順にソート
2. タスクの必要スキルレベル配列 \(B\) を降順にソート
3. 2つのポインタ \(i\)（スタッフ用）と \(j\)（タスク用）を用意
4. 以下を繰り返す：
   • \(A_i \geq B_j\) なら、スタッフ \(i\) にタスク \(j\) を割り当て、両方のポインタを進める
   • \(A_i < B_j\) なら、現在のスタッフはこのタスクを担当できないので、タスクのポインタだけ進める（より簡単なタスクを探す）
5. 成立したマッチング数 × \(C\) を出力

このアルゴリズムが正しい理由：スキルが高いスタッフから順に、担当可能な最も難しいタスクを割り当てることで、スキルの「余裕」を無駄にせず、できるだけ多くのマッチングを作れます。

計算量

• 時間計算量: \(O(N \log N + M \log M)\)
  • ソートに \(O(N \log N)\) と \(O(M \log M)\)
  • マッチング処理は各ポインタが最大で配列の長さ分しか進まないので \(O(N + M)\)
• 空間計算量: \(O(N + M)\)
  • 配列 \(A\) と \(B\) の保存に必要

実装のポイント

• ソートは降順で行うこと（昇順でも同様のロジックで解けますが、ポインタの動かし方が変わります）

• マッチングが成立しない場合、タスクのポインタ \(j\) だけを進めること（そのスタッフは後でより簡単なタスクとマッチングできる可能性があるため、スタッフのポインタは進めない…と思いがちですが、実は \(j\) を進めるのが正解。必要スキルが高いタスクを担当できないスタッフは、それより低いタスクも他のスタッフに任せた方が効率的）

• 最終的な売上は count * C で計算。オーバーフローに注意（Pythonでは問題なし）

  ソースコード

def solve():
    N, M, C = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    
    # スタッフのスキルレベルを降順にソート
    A.sort(reverse=True)
    # タスクの必要スキルレベルを降順にソート
    B.sort(reverse=True)
    
    # 貪欲法：スキルが高いスタッフから順に、必要スキルが高いタスクを割り当てる
    count = 0
    i = 0  # スタッフのインデックス
    j = 0  # タスクのインデックス
    
    while i < N and j < M:
        if A[i] >= B[j]:
            # スタッフiがタスクjを担当できる
            count += 1
            i += 1
            j += 1
        else:
            # スタッフiはタスクjを担当できない
            # より必要スキルが低いタスクを探す
            j += 1
    
    print(count * C)

solve()

---

この解説は claude4.5opus によって生成されました。