概要

\(N\) 個の荷物を \(N\) 台の台車にできるだけ多く載せる問題です。各台車には耐荷重以下の重さの荷物を \(1\) つだけ載せることができ、運べる荷物の最大個数を求めます。

考察

この問題は、「どの荷物をどの台車に割り当てるのが最適か」を考える典型的な貪欲法の問題です。

以下の戦略を考えてみましょう。 1. 軽い荷物から順に見ていく。 2. その荷物を載せられる台車のうち、最も耐荷重が小さいものを使う。

なぜこの方法が最適なのでしょうか。 例えば、軽い荷物をあえて耐荷重が非常に大きい台車に載せてしまうと、後から出てくる重い荷物を載せるための「余裕」を無駄に消費してしまいます。小さい荷物には「ギリギリ載るサイズの台車」を割り当てることで、大きな台車を重い荷物のために温存するのが賢い戦略です。

荷物の重さ \(W\) と台車の耐荷重 \(C\) をそれぞれ昇順（小さい順）にソートすることで、この「小さいものから順にマッチングさせる」処理を効率的に行うことができます。

アルゴリズム

1. 荷物の重さのリスト \(W\) と、台車の耐荷重のリスト \(C\) をそれぞれ昇順にソートします。
2. 2つのポインタ（荷物用の \(i\) と台車用の \(j\)）を準備します。初期値はどちらも \(0\) です。
3. 以下の操作を \(i < N\) かつ \(j < N\) である間繰り返します。
   • 荷物 \(i\) が台車 \(j\) に載る場合 (\(W_i \leq C_j\)): マッチング成立です。運べる個数を \(1\) 増やし、次の荷物と次の台車を見るために \(i\) と \(j\) を両方 \(1\) 進めます。
   • 荷物 \(i\) が台車 \(j\) に載らない場合 (\(W_i > C_j\)): 台車 \(j\) の耐荷重が足りません。荷物 \(i\) はこれ以降の荷物（\(W_i\) 以上の重さ）の中で最も軽いため、台車 \(j\) には今後どの荷物も載せることができません。よって、台車 \(j\) を諦めて \(j\) だけを \(1\) 進めます。
4. 最終的なカウントが答えとなります。

計算量

• 時間計算量: \(O(N \log N)\)
  • リストのソートに \(O(N \log N)\) かかります。
  • その後の2ポインタによる走査は \(O(N)\) です。
  • 全体としてソートの計算量が支配的になります。
• 空間計算量: \(O(N)\)
  • 入力された \(W\) と \(C\) を保持するために \(O(N)\) のメモリを使用します。

実装のポイント

• \(N\) が最大 \(2 \times 10^5\) と大きいため、Pythonでは input() よりも sys.stdin.read().split() などを用いて高速に入力を読み込むのが無難です。

• 2ポインタ法を用いることで、二重ループを避けて効率的にマッチングを判定しています。

  ソースコード

import sys

def solve():
    # 入力をすべて取得
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # Nを取得
    n = int(input_data[0])
    
    # 荷物の重さ W と台車の耐荷重 C を取得
    w = list(map(int, input_data[1:n+1]))
    c = list(map(int, input_data[n+1:2*n+1]))
    
    # 昇順にソート
    w.sort()
    c.sort()
    
    # 2ポインタ法を用いて、軽い荷物から順に、
    # それを載せられる最小の耐荷重を持つ台車を割り当てる
    ans = 0
    i = 0 # 荷物のインデックス
    j = 0 # 台車のインデックス
    
    while i < n and j < n:
        if w[i] <= c[j]:
            # 荷物 i を台車 j に載せられる場合
            ans += 1
            i += 1
            j += 1
        else:
            # 荷物 i が台車 j に載らない場合、より大きな台車を探す
            j += 1
            
    # 結果を出力
    print(ans)

if __name__ == '__main__':
    solve()

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