概要

この問題は、与えられた能力（最大重量 \(S_i\)）を持つ配達員と、特定の負荷（重量 \(D_j\)）を持つ依頼を、条件 \(S_i \geq D_j\) を満たすようにペアリングし、その最大件数を求める問題です。

考察

この問題を解くための鍵は、「どの配達員にどの依頼を割り当てるのが最も効率的か」という貪欲法（Greedy Algorithm）の考え方です。

重要な気づき

重い荷物を運べる能力の高い配達員は、軽い荷物も重い荷物も運ぶことができます。一方で、能力の低い配達員は軽い荷物しか運べません。 したがって、「能力の低い配達員でも運べる軽い荷物は、能力の低い人に任せて、能力の高い人は重い荷物のために温存しておく」のが最善の戦略となります。

なぜソートが必要か

適当な順番で割り当ててしまうと、能力の高い人が軽い荷物を担当してしまい、後から出てきた重い荷物を誰も運べなくなる可能性があります。 そこで、配達員の能力 \(S\) と依頼の重量 \(D\) を両方とも昇順（小さい順）に並べ替えることで、効率的なマッチングが可能になります。

アルゴリズム

ソート済みの配列に対して、「二つのポインタ（尺取り法の要領）」を用いて走査します。

1. 配達員の能力リスト \(S\) と、依頼の重量リスト \(D\) をそれぞれ昇順にソートします。
2. 配達員を指すポインタ worker_idx と、依頼を指すポインタ request_idx を \(0\) に初期化します。
3. 以下の処理を、どちらかのポインタが末尾に達するまで繰り返します。
   • もし、現在の配達員が現在の依頼を運べる場合（\(S[\text{worker\_idx}] \geq D[\text{request\_idx}]\)）：
     • 割り当て成功としてカウントを \(1\) 増やします。
     • 次の依頼と次の配達員を確認するため、両方のポインタを \(1\) 進めます。
   • 運べない場合（\(S[\text{worker\_idx}] < D[\text{request\_idx}]\)）：
     • 現在の配達員はその依頼を運べず、それ以降のより重い依頼も運べません。
     • より能力の高い配達員に期待するため、worker_idx だけを \(1\) 進めます。

計算量

• 時間計算量: \(O(N \log N + M \log M)\)
  • 配達員と依頼のソートにそれぞれ \(O(N \log N)\) と \(O(M \log M)\) かかります。
  • その後の二つのポインタによる走査は \(O(N + M)\) です。
  • 全体としてソートの計算量が支配的になりますが、制約の \(2 \times 10^5\) に対して十分高速に動作します。
• 空間計算量: \(O(N + M)\)
  • 入力された \(N\) 人の能力と \(M\) 件の重量を保持するためのメモリが必要です。

実装のポイント

• 高速な入出力: \(N, M\) が最大 \(2 \times 10^5\) と大きいため、Pythonでは sys.stdin.read().split() などを用いて一括で入力を読み込むと実行時間を短縮できます。

• ソートの順序: 今回は昇順で解説しましたが、降順（大きい順）にソートして「重い荷物を、それを運べるギリギリの能力を持つ配達員に割り当てる」という方針でも同様に解くことができます。

  ソースコード

import sys

def solve():
    # 入力をすべて取得
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 配達員の人数, M: 依頼の件数
    N = int(input_data[0])
    M = int(input_data[1])
    
    # S: 配達員の最大重量, D: 依頼の重量
    S = list(map(int, input_data[2:2+N]))
    D = list(map(int, input_data[2+N:2+N+M]))
    
    # 昇順にソートして、小さい方から貪欲にマッチングさせる
    S.sort()
    D.sort()
    
    worker_idx = 0
    request_idx = 0
    count = 0
    
    # 二つのポインタを用いて走査
    while worker_idx < N and request_idx < M:
        # 現在の配達員が現在の依頼を運べる場合
        if S[worker_idx] >= D[request_idx]:
            count += 1
            worker_idx += 1
            request_idx += 1
        else:
            # 運べない場合は、より大きい能力を持つ次の配達員を確認する
            worker_idx += 1
            
    # 最大件数を出力
    print(count)

if __name__ == '__main__':
    solve()

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