概要

荷物の重さ \(W_i\) と台車の耐荷重 \(C_j\) が与えられるとき、条件 \(W_i \le C_j\) を満たすように「荷物1つ＋台車1台」をできるだけ多く組み合わせる最大個数を求めます。

考察

この問題は「できるだけ多くペアを作る」二部マッチングに見えますが、一般の最大マッチングをすると重くなりがちです。今回は条件が \(W_i \le C_j\) という一次元の大小関係だけ なので、もっと簡単な貪欲法で解けます。

重要な気づきは次の通りです。

• 軽い荷物ほど乗せられる台車の候補が多い（制約がゆるい）。
• 逆に重い荷物は乗せられる台車が限られる（大きい耐荷重が必要）。

したがって、 - 小さい耐荷重の台車には、載せられる中で一番軽い荷物を載せる
のが自然です。これを守ると、将来の選択肢を最大限残せます。

素朴な方法がダメな理由

例えば各台車ごとに「載せられる荷物を探す」を愚直にやると、最悪で \(O(N^2)\) になります。
\(N \le 2 \times 10^5\) なので、\(N^2\) は現実的ではありません（TLE）。

この問題はソートして順に見ていくことで、探索を線形にできます。

具体例

• 荷物: \(W=[2,3,5]\)
• 台車: \(C=[3,4,5]\)

両方ソートして、 - 耐荷重 3 には最も軽い 2 を載せる（成功） - 耐荷重 4 には次に軽い 3 を載せる（成功） - 耐荷重 5 には次に軽い 5 を載せる（成功）

合計 3 個運べます。

もし耐荷重 3 に荷物 3 を載せてしまうと、耐荷重 4 に荷物 5 が載らず失敗するなど、貪欲の選び方が重要だと分かります。

アルゴリズム

1. 荷物の重さ配列 \(W\) と台車の耐荷重配列 \(C\) をそれぞれ昇順ソートする。
2. ポインタ \(i\) を「次に載せたい最も軽い未使用の荷物」の位置として 0 から開始する。
3. 台車を耐荷重の小さい順に見ていき、台車の耐荷重を cap とする。
   • もし \(i < N\) かつ \(W[i] \le cap\) なら、その荷物をこの台車に載せられるので
     • 答えを 1 増やす
     • \(i\) を 1 進める（次に軽い荷物へ）
   • そうでなければ、この台車にはどの未使用荷物も載せられない（今見ている荷物が最軽量なのに無理）のでスキップする。
4. 数え上げた個数が最大で運べる荷物数。

ポイントは「各台車に対して、載せられるなら最軽量の未使用荷物を割り当てる」ことです。これにより、重い荷物を載せるための大きい耐荷重の台車を温存できます。

計算量

• 時間計算量: \(O(N \log N)\)（\(W\) と \(C\) のソートが支配的、走査は \(O(N)\)）
• 空間計算量: \(O(1)\)（入力配列を除けば追加は定数、ソートの内部領域は言語処理系依存）

実装のポイント

• 両方をソートしてから、台車を小さい順に処理する。

• 荷物側はインデックス \(i\) で管理し、成功したときだけ \(i\) を進める（いわゆる二ポインタ）。

• W[i] > cap のときは、その台車では最軽量の荷物すら載らないため、以降の（より重い）荷物も載りません。よってその台車は諦めて次へ進めばよいです。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    W = list(map(int, input().split()))
    C = list(map(int, input().split()))

    W.sort()
    C.sort()

    i = 0
    ans = 0
    for cap in C:
        if i < N and W[i] <= cap:
            ans += 1
            i += 1

    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。