概要

\(N\) 人のスタッフと \(M\) 個のタスクを、スキルレベルの条件（スタッフのスキル \(\geq\) タスクの必要スキル）を満たすようにペアリングし、そのペアの総数を最大化して売上（ペア数 \(\times C\)）を求める問題です。

考察

この問題の核心は、「どのスタッフをどのタスクに割り当てるのが最も効率的か」という点にあります。

例えば、スキルの非常に高いスタッフが簡単なタスクを担当してしまうと、後から出てくる難しいタスクをこなせる人がいなくなってしまうかもしれません。そのため、以下の貪欲法の考え方が有効です。

1. 「スキルの低いスタッフ」から順に注目する。
2. そのスタッフがこなせるタスクの中で、「最も必要スキルが低いタスク」を割り当てる。

もし、あるスタッフが現在残っている中で最も簡単なタスクすらこなせない場合、そのスタッフはどのタスクも担当できないため、次の（よりスキルが高い）スタッフの出番となります。逆に、あるタスクをこなせるスタッフが複数いるなら、よりスキルの低いスタッフを割り当てることで、スキルの高いスタッフを温存するのが最適です。

この戦略を効率的に行うために、スタッフのスキルとタスクの必要スキルをあらかじめ昇順（小さい順）にソートしておくことが重要です。

アルゴリズム

ソート済みの配列に対して、2つのポインタ（現在見ているスタッフの番号とタスクの番号）を用いて走査します。

1. スタッフのスキル \(A\) とタスクの必要スキル \(B\) をそれぞれ昇順にソートします。
2. スタッフを指すポインタ staff_idx と、タスクを指すポインタ task_idx を \(0\) に初期化します。
3. 以下の操作を、どちらかのポインタが最後まで到達するまで繰り返します。
   • もし A[staff_idx] >= B[task_idx] ならば：
     • そのスタッフはそのタスクを担当できます。
     • 担当したペア数を \(+1\) し、両方のポインタを次に進めます。
   • そうでなければ（スキルが足りない場合）：
     • そのスタッフは現在のタスクを担当できません。
     • よりスキルの高いスタッフを試すため、staff_idx だけを次に進めます。
4. 最終的なペア数に \(C\) を掛けたものが答えです。

計算量

• 時間計算量: \(O(N \log N + M \log M)\)
  • スタッフとタスクのソートに \(O(N \log N)\) および \(O(M \log M)\) かかります。
  • 2つのポインタによる走査は \(O(N + M)\) です。
  • 全体としてソートの計算量が支配的になります。
• 空間計算量: \(O(N + M)\)
  • 入力されたスキルレベルを保持するリストのサイズに依存します。

実装のポイント

• 高速な入出力: \(N, M\) が最大 \(2 \times 10^5\) と大きいため、Pythonでは input() を繰り返すよりも sys.stdin.read().split() などで一括して入力を取得する方が実行時間を短縮できます。

• ソートの順序: 降順（大きい順）でソートして考えることも可能ですが、昇順で「弱い者同士」からマッチングさせる方が直感的で実装ミスも少なくなります。

  ソースコード

import sys

def solve():
    # 入力を高速に読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    C = int(input_data[2])
    
    # スタッフのスキルレベル A
    A = []
    for i in range(N):
        A.append(int(input_data[3 + i]))
        
    # タスクの必要スキルレベル B
    B = []
    for j in range(M):
        B.append(int(input_data[3 + N + j]))
        
    # スキルレベルを昇順にソート
    A.sort()
    B.sort()
    
    # 2つのポインタを用いて、割り当て可能な最大タスク数を求める
    # 貪欲法：スキルレベルの低いスタッフから順に、
    # そのスタッフがこなせる最も必要スキルレベルが低いタスクを割り当てる
    staff_idx = 0
    task_idx = 0
    count = 0
    
    while staff_idx < N and task_idx < M:
        if A[staff_idx] >= B[task_idx]:
            # スタッフがタスクを担当できる場合
            count += 1
            staff_idx += 1
            task_idx += 1
        else:
            # スタッフのスキルが足りない場合、次の（よりスキルの高い）スタッフを確認する
            staff_idx += 1
            
    # 最大売上金額を出力
    print(count * C)

if __name__ == "__main__":
    solve()

この解説は gemini-3-flash-thinking によって生成されました。