概要

\(N\) 個の宝箱と \(M\) 本の鍵があり、鍵の開錠能力が宝箱の錠前強度以上であれば開けることができる。開けられる宝箱の最大数を求めよ。

考察

この問題の目的は、「使えるだけ多くの宝箱を開ける」ことです。
各宝箱には開錠能力がそれ以上の鍵が必要であり、鍵は一度使ったら再利用できないので、うまく対応づける必要があります。

素朴な考え（貪欲にマッチング）

最初に思いつくのは、各宝箱に対して「使える鍵の中で最も余っているもの」を使う方法です。しかし、これをナイーブに実装すると、毎回使える鍵を探すのに \(O(M)\) かかり、全体で \(O(NM)\) となって間に合いません。

改善策：ソートして順番に処理

重要な観察は次の通りです： - 「弱い宝箱（\(C_i\) が小さい）」には「使える鍵がたくさんある」 - 「強い宝箱」は「使える鍵が限られる」

つまり、宝箱を強度が低い順に並べて、それに使える最小の鍵を割り当てていくのが最適です。これにより、強い宝箱のために弱い鍵を無駄遣いしてしまうことを避けられます。

そこで以下のように考えます： 1. 宝箱の強度 \(C\) と鍵の開錠能力 \(R\) をそれぞれ昇順にソートする。 2. 弱い宝箱から順に見て行き、それに対応できる最小の鍵（まだ使っていない中で \(R_j \geq C_i\) を満たす最小の \(j\)）を使います。 3. これにより、無駄なく鍵を消費しながら最大数を開けることができます。

効率的な実装のために

鍵のリスト \(R\) はソートされているので、「まだ使っていない鍵の中で、ある値 \(c\) 以上となる最小の位置」を高速に探すことができます。これは 二分探索（bisect.bisect_left） を使うことで可能です。

アルゴリズム

1. 宝箱の強度リスト \(C\) と鍵の開錠能力リスト \(R\) をそれぞれ昇順にソートする。
2. 鍵の使用開始位置 r_index を 0 とする。
3. 各宝箱の強度 \(c\) について、以下を行う：
   • \(R\) の r_index 以降で初めて \(c\) 以上になる位置を二分探索で探す。
   • その位置が存在すれば、その鍵を使って宝箱を開けたことにする（count += 1）、そして r_index を1進める。
4. 最終的な count を出力する。

このアルゴリズムにより、各宝箱に対して必要な鍵を最適に割り当てることができます。

例

入力例：

N = 3, M = 4
C = [3, 1, 4]
R = [2, 5, 1, 3]

ソート後：

C = [1, 3, 4]
R = [1, 2, 3, 5]

処理過程： - 宝箱1 (\(c=1\)) → 鍵1 (\(r=1\)) で開ける（次は index=1 から） - 宝箱2 (\(c=3\)) → 鍵3 (\(r=3\)) で開ける（次は index=3 から） - 宝箱3 (\(c=4\)) → 鍵4 (\(r=5\)) で開ける（次は index=4 から）

→ 合計 3 個開けられる。

計算量

• 時間計算量: \(O(N \log N + M \log M)\) （ソートと二分探索のコスト）
• 空間計算量: \(O(1)\) （追加の大きな配列を使用しない）

実装のポイント

• C と R は必ず昇順にソートすること。
• bisect.bisect_left(R, c, r_index) のように、検索範囲を限定することで効率よく未使用の鍵の中から探せる。
• 鍵を使った後は r_index を進めて使い回しを防ぐ。

ソースコード

import bisect

N, M = map(int, input().split())
C = list(map(int, input().split()))
R = list(map(int, input().split()))

C.sort()
R.sort()

count = 0
r_index = 0

for c in C:
    r_index = bisect.bisect_left(R, c, r_index)
    if r_index < M:
        count += 1
        r_index += 1

print(count)

---

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