概要

宝箱の強度 \(C_i\) と鍵の能力 \(R_j\) が与えられるとき、各鍵を高々1回使って開けられる宝箱の最大個数を求めます。
「小さい宝箱から順に、開けられる最小の鍵を割り当てる」貪欲法で最大数を達成できます。

考察

重要な気づき

宝箱 \(i\) を開けるには \(C_i \le R_j\) が必要です。ここで「どの鍵をどの宝箱に割り当てるか」は組合せが膨大ですが、次の方針が最適になります：

• 強度が小さい宝箱ほど開けやすい
  
• ある宝箱を開けるために、必要以上に能力の高い鍵を使うと、後で本当に高い能力が必要な宝箱が開けられなくなる

したがって、 - 宝箱を強度の小さい順に見ていき、開けられる鍵のうち最も能力が小さいものを使う のが自然で、これが最適になります（資源を無駄遣いしない戦略）。

素朴な方法がダメな理由

例えば「各宝箱について使える鍵を探す」を愚直にやると、最悪で \(O(NM)\)（\(2\times 10^5\) 同士なので到底無理）になります。
また、一般の最大マッチングとして解くのも重すぎますが、この問題は条件が「\(C_i \le R_j\)」という一次元の大小関係なので、ソート＋貪欲で解けます。

具体例

• 宝箱: \(C=[2,5,6]\)
• 鍵: \(R=[1,5,7]\)

小さい順に見ると、 - 宝箱2は鍵5で開ける（鍵7を温存） - 宝箱5は（残り鍵7で）開ける - 宝箱6はもう鍵がない
合計2個。ここで宝箱2に鍵7を使うと、宝箱5が開けられず1個になってしまい損です。

アルゴリズム

1. 宝箱の強度配列 \(C\) を昇順にソートする
2. 鍵の能力配列 \(R\) を昇順にソートする
3. 2つのポインタ \(i, j\) を用意する（\(i\) は宝箱、\(j\) は鍵を指す）
4. 次を繰り返す：
   • もし \(R_j \ge C_i\) なら、この鍵でこの宝箱を開けられるので割り当てる
     → 回数を +1、\(i\) と \(j\) を両方進める
   • そうでなければ鍵が弱すぎるので、この鍵はどの（今後のより強い）宝箱も開けられない
     → \(j\) だけ進めて次の鍵を試す
5. どちらかが尽きたら終了し、割り当て数が答え

この方法は「最も弱い宝箱から順に、使える最も弱い鍵を当てる」ことを常に行っており、鍵の能力を無駄にしないため最適です。

計算量

• 時間計算量: \(O(N\log N + M\log M)\)（ソートが支配的、走査は \(O(N+M)\)）
• 空間計算量: \(O(1)\)（ソート用を除けば追加領域は定数）

実装のポイント

• \(C, R\) を必ず昇順ソートしてから二重ポインタで走査します。

• while i < N and j < M: の条件で範囲外アクセスを防ぎます。

• \(R_j < C_i\) のときは宝箱側ではなく鍵側を進めます（この鍵は今後も使えないため）。

  ソースコード

import sys

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

    i = j = 0
    ans = 0
    while i < N and j < M:
        if R[j] >= C[i]:
            ans += 1
            i += 1
            j += 1
        else:
            j += 1

    print(ans)

if __name__ == "__main__":
    main()

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