概要

荷物の重さと台車の耐荷重が与えられ、各台車に最大1つの荷物を載せられる条件で、運べる荷物の最大個数を求める問題です。

考察

この問題は、各荷物を耐荷重以上の台車に割り当てる最大マッチング問題として考えることができます。素朴なアプローチとして、すべての可能な割り当てを試す方法がありますが、\(N\)が最大20万と大きいため、\(O(N^2)\)の計算量では実行時間制限に間に合いません。

重要な観察は、最適な割り当てでは「軽い荷物を小さい耐荷重の台車に割り当てる」方が効率的だということです。重い荷物を割り当てるには大きい耐荷重の台車が必要ですが、軽い荷物は小さい耐荷重の台車でも運べるため、大きい耐荷重の台車は重い荷物用に残しておくべきです。

アルゴリズム

1. 荷物の重さリスト\(W\)と台車の耐荷重リスト\(C\)をそれぞれソートする
2. 荷物を軽い方から順に、それに対応できる最小の耐荷重を持つ台車を割り当てていく
3. 具体的には、荷物\(i\)に対して、耐荷重\(C_j \geq W_i\)となる最小の\(j\)を探す
4. 対応する台車が見つかったら、カウントを増やし、次の台車に進む
5. これをすべての荷物に対して行う

この貪欲法により、最大個数の荷物を運ぶことができます。ソートすることで、各荷物に対して最適な台車を線形時間で見つけることが可能になります。

計算量

• 時間計算量: \(O(N \log N)\)（ソートに\(O(N \log N)\)、貪欲な割り当てに\(O(N)\)）
• 空間計算量: \(O(N)\)（入力データを格納するための配列）

実装のポイント

• ソート後の貪欲なマッチングが鍵となります

• 台車のインデックスjをループ外で管理し、各荷物に対して条件を満たす最小の台車を探します

• 台車がなくなったら即座にループを抜けることで無駄な処理を省きます

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    W = list(map(int, data[1:1+n]))
    C = list(map(int, data[1+n:1+2*n]))
    
    W.sort()
    C.sort()
    
    count = 0
    j = 0
    for i in range(n):
        while j < n and W[i] > C[j]:
            j += 1
        if j >= n:
            break
        count += 1
        j += 1
        
    print(count)

if __name__ == "__main__":
    main()

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