概要

\(N\) 個の宝箱と \(M\) 本の鍵があり、鍵の開錠能力が錠前の強度以上なら開けられるとき、最大でいくつの宝箱を開けられるかを求める問題です。各鍵は1回しか使えません。

考察

重要な気づき

この問題はマッチング問題の一種です。鍵と宝箱を1対1で対応させて、できるだけ多くの宝箱を開けたいです。

素朴なアプローチの問題点

全ての鍵と宝箱の組み合わせを試すと、\(O(N \times M)\) や、最悪の場合はさらに大きな計算量になり、\(N, M\) が最大 \(2 \times 10^5\) のときにTLEになる可能性があります。

解決の方針：貪欲法

「弱い錠前から順に、開けられる鍵の中で最も弱い鍵を使う」 という貪欲法が最適です。

なぜこれが正しいのでしょうか？

直感的な説明： - 強い鍵は弱い宝箱も強い宝箱も開けられる「万能選手」 - 弱い鍵は弱い宝箱しか開けられない「専門家」 - 弱い宝箱には「専門家」を使い、「万能選手」は後のために取っておくのが得

具体例： - 宝箱の強度: \([10, 50]\) - 鍵の能力: \([30, 60]\)

弱い宝箱（強度10）を強い鍵（能力60）で開けると、強い宝箱（強度50）を開ける鍵がなくなります。 弱い宝箱を弱い鍵（能力30）で開ければ、強い宝箱も強い鍵で開けられ、2個開けられます。

アルゴリズム

1. 宝箱の錠前強度 \(C\) を昇順にソート
2. 鍵の開錠能力 \(R\) を昇順にソート
3. 弱い宝箱から順に見ていく
4. 各宝箱に対して、「まだ使っていない鍵の中で、その宝箱を開けられる最小の鍵」を使う
5. 開けられた宝箱の数をカウント

宝箱(ソート済): [10, 50, 80]
鍵(ソート済):   [30, 40, 60]

宝箱10 → 鍵30で開ける ✓
宝箱50 → 鍵40は使えない(40<50)、鍵60で開ける ✓
宝箱80 → 残りの鍵なし ✗

答え: 2個

計算量

• 時間計算量: \(O(N \log N + M \log M)\)

  • 宝箱のソート: \(O(N \log N)\)
  • 鍵のソート: \(O(M \log M)\)
  • マッチング処理: \(O(N + M)\)（各要素を最大1回ずつ見る）

• 空間計算量: \(O(N + M)\)

  • 宝箱と鍵のリストを保持

実装のポイント

1. 二重ループに見えるが線形時間

   • key_idx は増加するのみで、戻ることがない
   • 外側のループで \(N\) 回、内側の while は合計で最大 \(M\) 回しか実行されない
   • よって全体で \(O(N + M)\)

2. 鍵のインデックス管理

   • 一度使った鍵は再利用できないので、key_idx を進めたら戻さない

   • 宝箱を開けられなかった場合も、その鍵より弱い鍵は今後も使えないので key_idx は戻さなくてよい

     ソースコード

def solve():
    N, M = map(int, input().split())
    C = list(map(int, input().split()))
    R = list(map(int, input().split()))
    
    # 宝箱の錠前強度と鍵の開錠能力をソート
    C.sort()
    R.sort()
    
    # 貪欲法：弱い錠前から順に、開けられる鍵の中で最も弱い鍵を使う
    count = 0
    key_idx = 0
    
    for box_strength in C:
        # この宝箱を開けられる鍵を探す（R[key_idx] >= box_strength となる最初の鍵）
        while key_idx < M and R[key_idx] < box_strength:
            key_idx += 1
        
        if key_idx < M:
            # 開けられる鍵が見つかった
            count += 1
            key_idx += 1
    
    print(count)

solve()

---

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