概要

\(N\) 個の荷物と \(N\) 台の台車があり、それぞれ重さと耐荷重が与えられます。
荷物を台車にうまく割り当てて、運べる荷物の最大個数を求めます。

考察

この問題は「どの荷物をどの台車に割り当てるか」という組み合わせ最適化の問題です。
素朴な方法として、全ての割り当て方を試すことが考えられますが、その計算量は非常に大きくなります（\(N!\) 通り）。
そのため、効率的な方法が必要です。

重要な観察として、「軽い荷物から順に、それを受け入れられる最も耐荷重が小さい台車に割り当てる」貪欲法が有効です。
つまり、

• 荷物の重さ \(W\) を昇順にソート
• 台車の耐荷重 \(C\) を昇順にソート

した上で、先頭から順に対応させていけば良いのです。

なぜこれで最適解が得られるのかというと、軽い荷物ほど受け入れ可能な台車の選択肢が多く、
重い荷物ほど選べる台車が限られるので、軽いものから優先的に処理するのが最適だからです。

たとえば以下のような具体例を見てみましょう。

例：

荷物の重さ：[2, 5, 3]
台車の耐荷重：[6, 2, 4]

ソート後：

荷物：[2, 3, 5]
台車：[2, 4, 6]

• 荷物2 → 台車2（OK）
• 荷物3 → 台車4（OK）
• 荷物5 → 台車6（OK）

このようにすべて運ぶことができます。

もし逆に、重い荷物から割り当てようとすると、
たとえば荷物5を台車6に使ってしまい、残った軽い荷物を載せられない台車に無駄にすることがあります。

アルゴリズム

1. 荷物のリスト \(W\) と台車のリスト \(C\) をそれぞれ昇順にソートします。
2. 両方のリストの先頭から順番に見ていき、現在の荷物が現在の台車に乗るなら割り当てます。
3. 割り当てたら次の荷物と次の台車に進みます。
4. 荷物が乗らない場合は、その台車は飛ばして次の台車を見ます。
5. この操作を繰り返して、何個の荷物を運べるかをカウントします。

これは貪欲法と呼ばれる典型的なアルゴリズムで、今回の問題において最適性が保証されています。

計算量

• 時間計算量: \(O(N \log N)\) （ソートが支配的）
• 空間計算量: \(O(N)\) （入力配列の記憶領域）

実装のポイント

• 入力を高速に読み込むために sys.stdin.read を使用しています。
• ソート後の添字管理を誤らないよう、2つのポインタ（i, j）を使ってシミュレーションします。
• Python では sort() が破壊的であることに注意しましょう。

## ソースコード

```python
import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    W = list(map(int, data[1:N+1]))
    C = list(map(int, data[N+1:2*N+1]))
    
    # 荷物と台車をそれぞれソート
    W.sort()
    C.sort()
    
    # 貪欲法でマッチング
    i = 0  # 荷物のインデックス
    j = 0  # 台車のインデックス
    count = 0
    
    while i < N and j < N:
        if W[i] <= C[j]:
            count += 1
            i += 1
            j += 1
        else:
            j += 1
    
    print(count)

if __name__ == "__main__":
    main()

---

この解説は qwen3-coder-480b によって生成されました。