概要

各学生の学年 \(S_i\) に対して、借りられる本（\(T_j \leq S_i\) を満たす本）の冊数を効率的に求める問題です。ソートと二分探索を組み合わせて解きます。

考察

問題の本質

学生 \(i\) が本 \(j\) を借りられる条件は \(S_i \geq T_j\) です。つまり、各学生について「自分の学年以下の必要学年を持つ本が何冊あるか」を数えればよいです。

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

最も単純な方法は、各学生について全ての本をチェックすることです：

for i in range(N):
    count = 0
    for j in range(M):
        if S[i] >= T[j]:
            count += 1
    print(count)

この方法の計算量は \(O(N \times M)\) です。\(N, M\) が最大 \(2 \times 10^5\) のとき、最悪で \(4 \times 10^{10}\) 回の操作が必要となり、TLE（時間制限超過）になります。

解決のアイデア

「\(S_i\) 以上の値を持つ \(T_j\) の個数」を高速に求めたいです。

重要な気づき: 配列 \(T\) をソートしておけば、\(T_j \leq S_i\) を満たす要素は配列の先頭から連続して並びます。

例えば、\(T = [3, 1, 4, 2]\) をソートすると \(T = [1, 2, 3, 4]\) になります。 - \(S_i = 2\) のとき、\(T_j \leq 2\) を満たすのは \([1, 2]\) の 2冊 - \(S_i = 3\) のとき、\(T_j \leq 3\) を満たすのは \([1, 2, 3]\) の 3冊

この「\(S_i\) 以下の要素が何個あるか」は二分探索で \(O(\log M)\) で求められます。

アルゴリズム

1. 本の必要学年の配列 \(T\) を昇順にソートする
2. 各学生 \(i\) について：
   • ソート済み \(T\) に対して、\(S_i\) 以下の要素の個数を二分探索で求める
   • bisect_right(T, S[i]) は「\(T\) の中で \(S_i\) より大きい最初の要素のインデックス」を返す
   • これは「\(S_i\) 以下の要素の個数」と一致する

具体例

\(N=3, M=4\)、\(S = [2, 4, 1]\)、\(T = [3, 1, 4, 2]\) の場合：

1. \(T\) をソート → \(T = [1, 2, 3, 4]\)
2. 学生1（\(S_1 = 2\)）: bisect_right([1,2,3,4], 2) = 2 → 2冊
3. 学生2（\(S_2 = 4\)）: bisect_right([1,2,3,4], 4) = 4 → 4冊
4. 学生3（\(S_3 = 1\)）: bisect_right([1,2,3,4], 1) = 1 → 1冊

計算量

• 時間計算量: \(O(M \log M + N \log M)\)
  • \(T\) のソートに \(O(M \log M)\)
  • 各学生に対する二分探索が \(O(\log M)\) で、\(N\) 人分で \(O(N \log M)\)
• 空間計算量: \(O(N + M)\)
  • 配列 \(S\) と \(T\) の保存に必要

実装のポイント

• bisect_right(T, x) は、ソート済み配列 \(T\) において \(x\) 以下の要素の個数を返します

• bisect_left(T, x) を使うと \(x\) 未満の要素の個数になるため、今回は bisect_right が適切です

• 本の順番は答えに影響しないため、\(T\) をソートしても問題ありません（学生の順番は出力に影響するため \(S\) はソートしません）

  ソースコード

import bisect

def main():
    N, M = map(int, input().split())
    S = list(map(int, input().split()))
    T = list(map(int, input().split()))
    
    # Tをソートして二分探索で使う
    T.sort()
    
    # 各学生について、借りられる本の数を計算
    for i in range(N):
        # S[i] >= T[j] を満たすT[j]の数を求める
        # ソート済みTの中で、S[i]以下の要素の数がそれに該当
        count = bisect.bisect_right(T, S[i])
        print(count)

if __name__ == "__main__":
    main()

---

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