概要

配達員と配達依頼を条件に合うようにマッチングさせ、最大の割り当て数を求める問題です。

考察

この問題は、条件を満たすように最大マッチングを見つける問題です。各配達員は高々1つの依頼しか担当できず、各依頼も高々1人の配達員にしか割り当てられません。また、配達員 \(i\) が依頼 \(j\) を担当できる条件は \(S_i \geq D_j\) です。

素朴なアプローチとして、すべての可能な組み合わせを試す方法が考えられますが、\(N\) と \(M\) が最大で \(2 \times 10^5\) と大きいため、\(O(N \times M)\) の計算量では時間内に解くことができません。

重要な観察は、より多くの依頼を割り当てるためには、各配達員にはできるだけ小さい荷物を割り当てた方が良いということです。つまり、配達員の能力 \(S_i\) と荷物の重量 \(D_j\) をそれぞれソートし、貪欲法（Greedy Algorithm）を用いて小さい方から順にマッチングさせていくことで、効率的に最大マッチング数を求めることができます。

アルゴリズム

1. 配達員の最大重量 \(S\) と依頼の荷物重量 \(D\) をそれぞれ昇順にソートします。
2. ソートされた \(S\) と \(D\) に対して、2つのポインタ \(i\) (配達員用) と \(j\) (依頼用) を用意します。
3. \(i\) と \(j\) がそれぞれ配列の範囲内である間、以下を繰り返します：
   • 現在の配達員 \(S[i]\) が現在の依頼 \(D[j]\) 以上であれば、マッチング成功とし、\(count\) を増やし、\(j\) を進めます。
   • 次の配達員を調べるため、\(i\) を常に進めます。
4. 最終的な \(count\) が最大割り当て数となります。

この貪欲法が正しく動作する理由は、ソート済みの配列において、小さい荷物から順に、それを運べる最小の配達員を割り当てていくことが最適だからです。これにより、能力の高い配達員をより重い荷物のために温存することができます。

計算量

• 時間計算量: \(O(N \log N + M \log M)\)
  • ソートに \(O(N \log N)\) と \(O(M \log M)\) の時間がかかり、その後の貪欲法の処理は \(O(N + M)\) です。
• 空間計算量: \(O(N + M)\)
  • 配列 \(S\) と \(D\) を格納するためのメモリが必要です。

実装のポイント

• 標準入力からデータを読み取る際、一度に全てのデータを読み込んでから処理すると効率的です。

• ソートには組み込み関数の sort() を使用します。これは非常に効率的なTimSortアルゴリズムを使用しています。

• ポインタ \(i\) と \(j\) をうまく管理することで、線形時間でマッチングを行うことができます。

  ソースコード

def main():
    import sys
    data = sys.stdin.read().split()
    n = int(data[0])
    m = int(data[1])
    S = list(map(int, data[2:2+n]))
    D = list(map(int, data[2+n:2+n+m]))
    
    S.sort()
    D.sort()
    
    count = 0
    i = 0
    j = 0
    
    while i < n and j < m:
        if S[i] >= D[j]:
            count += 1
            j += 1
        i += 1
        
    print(count)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。