概要

\(N\) 個の宝箱（強度 \(C_i\)）と \(M\) 本の鍵（能力 \(R_j\)）があり、鍵の能力が宝箱の強度以上であれば開錠できます。各鍵は一度しか使えないという条件下で、開けられる宝箱の最大数を求める問題です。

考察

この問題のポイントは、「どの鍵をどの宝箱に割り当てるのが最も効率的か」を考えることです。

まず、強度の低い（開けやすい）宝箱から順に考えてみましょう。ある宝箱を開ける際、その宝箱を開けられる能力を持つ鍵が複数あるなら、「その宝箱を開けられる鍵の中で、最も能力が低いもの」を使うのが最善です。なぜなら、能力が高い鍵は、後に出てくるより強固な宝箱を開けるために温存しておいた方が得だからです。

逆に、ある鍵に注目したとき、その鍵で開けられない宝箱は、それ以降のより能力の低い鍵でも当然開けることができません。

このような「その場その場で最善の選択をする」手法を貪欲法（Greedy Algorithm）と呼びます。宝箱の強度と鍵の能力をそれぞれ昇順（小さい順）に並べ替えることで、この貪欲な戦略を効率的にシミュレーションできます。

アルゴリズム

1. 宝箱の強度リスト \(C\) を昇順にソートします。
2. 鍵の能力リスト \(R\) を昇順にソートします。
3. 2つのポインタ（宝箱を指す chest_ptr と鍵を指す key_ptr）を先頭（0）にセットします。
4. 以下の操作を、どちらかのポインタが末尾に達するまで繰り返します。
   • もし R[key_ptr] >= C[chest_ptr] ならば：
     • その鍵で宝箱を開けることができます。
     • 開けた宝箱の数を +1 し、次の宝箱と次の鍵を調べるために両方のポインタを 1 進めます。
   • そうでなければ（鍵の能力が足りない場合）：
     • 現在の鍵では今の宝箱（およびそれ以降のより強い宝箱）を開けることができません。
     • この鍵は諦めて、より能力の高い次の鍵を試すために key_ptr のみを 1 進めます。
5. 最終的なカウントを出力します。

計算量

• 時間計算量: \(O(N \log N + M \log M)\)
  • 宝箱と鍵のソートに \(O(N \log N)\) および \(O(M \log M)\) かかります。
  • その後の2つのポインタによる走査は \(O(N + M)\) です。
  • 全体としてソートの計算量が支配的になります。
• 空間計算量: \(O(N + M)\)
  • 入力された宝箱と鍵の情報をリストに保持するために必要なメモリ量です。

実装のポイント

• 高速な入出力: \(N, M\) が最大 \(2 \times 10^5\) と比較的大きいため、Python では sys.stdin.read().split() などを用いて一括で入力を読み込むと実行時間を短縮できます。

• ソートの重要性: 貪欲法を適用するためには、必ず昇順にソートされている必要があります。ソートを忘れると、最適なペアを見つけることができず、誤った答え（WA）となります。

  ソースコード

import sys

def main():
    # 全ての入力を一度に読み込み、空白で分割してリストにします。
    # これにより、大量の入力データを高速に処理することが可能です。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 宝箱の個数 N と 鍵の本数 M を取得します。
    N = int(input_data[0])
    M = int(input_data[1])
    
    # 各宝箱の錠前の強度 C と 各鍵の開錠能力 R をリストとして取得します。
    C = list(map(int, input_data[2:2+N]))
    R = list(map(int, input_data[2+N:2+N+M]))
    
    # 強度と能力をそれぞれ昇順にソートします。
    # 貪欲法（Greedy Algorithm）を適用するためにソートが必要です。
    C.sort()
    R.sort()
    
    chest_ptr = 0  # 宝箱を指すポインタ
    key_ptr = 0    # 鍵を指すポインタ
    opened_chests = 0  # 開けることができた宝箱の数
    
    # 2つのポインタを用いて、可能な限り多くの宝箱を鍵に割り当てます。
    while chest_ptr < N and key_ptr < M:
        if R[key_ptr] >= C[chest_ptr]:
            # 現在の鍵で現在の宝箱を開けることができる場合
            # このペアを確定させ、次の宝箱と次の鍵へ進みます。
            opened_chests += 1
            chest_ptr += 1
            key_ptr += 1
        else:
            # 現在の鍵が現在の宝箱に対して弱すぎる場合
            # 宝箱はソートされているため、この鍵はこれ以降のどの宝箱も開けられません。
            # したがって、より能力の高い次の鍵を試します。
            key_ptr += 1
            
    # 最大の宝箱の個数を出力します。
    print(opened_chests)

if __name__ == '__main__':
    main()

この解説は gemini-3-flash-preview によって生成されました。