概要

\(N\) 個の荷物と \(N\) 台の台車が与えられ、荷物の重さが台車の耐荷重以下のときに載せられるという条件のもと、最大何個の荷物を運べるかを求めるマッチング問題です。

考察

重要な気づき：貪欲法が最適

まず、すべての荷物と台車のペアを総当たりで試すと \(O(N!)\) 通りになり、\(N\) が最大 \(2 \times 10^5\) なので到底間に合いません。

ここで重要な観察があります：

軽い荷物ほど載せやすい（多くの台車に載せられる）ので、軽い荷物から順に、できるだけ耐荷重の小さい台車に割り当てるのが最適

これは直感的に理解できます。耐荷重の大きい台車は「貴重な資源」であり、重い荷物にしか対応できない場合があります。軽い荷物に大きな台車を使ってしまうと、重い荷物が載せられなくなる可能性があります。

具体例

荷物の重さ: \([2, 5, 8]\)、台車の耐荷重: \([3, 6, 7]\) の場合

• ソート後: \(W = [2, 5, 8]\), \(C = [3, 6, 7]\)
• 荷物 \(2\) → 台車 \(3\)（載せられる ✓）
• 荷物 \(5\) → 台車 \(6\)（載せられる ✓）
• 荷物 \(8\) → 台車 \(7\)（載せられない ✗）
• 結果: 2個

もし荷物 \(2\) を台車 \(6\) に載せてしまうと、荷物 \(5\) は台車 \(7\) に載り、荷物 \(8\) は載せられず、結果は同じ2個です。しかし、小さい台車から使う方が無駄がなく、常に最適になります。

アルゴリズム

1. 荷物の重さ \(W\) を昇順にソートする
2. 台車の耐荷重 \(C\) を昇順にソートする
3. 二つのポインタ（Two Pointers） を使って走査する：
   • ポインタ \(i\) は台車を、ポインタ \(j\) は荷物を指す
   • 台車 \(i\) を順に見ていき、現在の荷物 \(j\) が台車 \(i\) に載せられる（\(W[j] \leq C[i]\)）なら、マッチングしてカウントを増やし、次の荷物 \(j+1\) に進む
   • 載せられなければ、次のより大きい台車 \(i+1\) を試す
4. カウントが答え

この貪欲法は「軽い荷物を耐荷重の小さい台車から順にマッチングする」戦略に対応しています。

計算量

• 時間計算量: \(O(N \log N)\)（ソートが支配的。走査部分は \(O(N)\)）
• 空間計算量: \(O(N)\)（ソート済み配列の保持）

実装のポイント

• ソート後に二つのポインタで線形に走査するだけなので、実装は非常にシンプルです

• ポインタ \(j\)（荷物側）はマッチングが成立したときだけ進み、ポインタ \(i\)（台車側）は毎回進むことに注意してください。これにより、各台車に対して「今まだ割り当てられていない最も軽い荷物」を載せようと試みる動作になります

• sys.stdin.read() で入力を一括読み込みすることで、Python でも高速に動作します

  ソースコード

import sys

def main():
    input_data = sys.stdin.read().split()
    N = int(input_data[0])
    W = sorted(int(input_data[i+1]) for i in range(N))
    C = sorted(int(input_data[i+1+N]) for i in range(N))
    
    count = 0
    j = 0
    for i in range(N):
        if j < N and W[j] <= C[i]:
            count += 1
            j += 1
    
    print(count)

main()

---

この解説は claude4.6opus-thinking によって生成されました。