概要

各学生の学年 \(S_i\) に対して、「条件 \(T_j \le S_i\) を満たす本が何冊あるか」を全員分求める問題です。
本の必要学年 \(T\) をうまく前処理して、高速に個数を数えます。

考察

学生 \(i\) が借りられる本は、条件 \(S_i \ge T_j\) を満たす本すべてです。つまり学生ごとに「\(T_j \le S_i\) の個数」を数えればよいです。

素朴にやると、各学生について全ての本を確認して - 学生 \(N\) 人 × 本 \(M\) 冊で \(O(NM)\)

となります。制約は \(N, M \le 2 \times 10^5\) なので、最悪で \(4 \times 10^{10}\) 回程度の比較になり、時間内に終わりません（TLE）。

ここで重要な観察は次の通りです： - 本の必要学年 \(T_j\) を昇順にソートしておけば、ある学年 \(s\) に対して「\(T_j \le s\) の本」は配列の先頭から連続して並ぶ。 - よって「\(s\) 以下の要素が何個あるか」は二分探索で高速に求められる。

例えば \(T = [1, 2, 2, 5, 7]\) のとき、 - \(s=2\) なら \(2\) 以下は \([1,2,2]\) の 3 個 - \(s=6\) なら \(6\) 以下は \([1,2,2,5]\) の 4 個 のように、境界位置（右端）を探せば個数が分かります。

アルゴリズム

1. 本の必要学年配列 \(T\) を昇順にソートする。
2. 各学生の学年 \(s = S_i\) について、二分探索で
   • \(T\) のうち \(s\) 以下の要素数を求める。
3. その個数を出力する。

実装では bisect_right(T, s) を使います。これは「ソート済み配列 T に対し、値 s を右側に挿入できる位置（= s 以下の要素数）」を返します。
よって答えはそのまま bisect_right(T, s) になります。

計算量

• 時間計算量: ソートに \(O(M \log M)\)、各学生の二分探索に \(O(N \log M)\)、合計で \(O(M \log M + N \log M)\)
• 空間計算量: \(O(M)\)（ソートした \(T\) を保持。出力用も含めれば \(O(N+M)\) 程度）

実装のポイント

• bisect_right を使うことで「\(T_j \le S_i\) の個数」をそのまま得られます（bisect_left だと「\(T_j < S_i\) の個数」寄りになるので注意）。

• 入力が大きいので sys.stdin.buffer.read() でまとめて読み込むと高速です。

• 出力も "\n".join(...) でまとめて書くと速くなります。

  ソースコード

import sys
from bisect import bisect_right

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, M = data[0], data[1]
    S = data[2:2+N]
    T = data[2+N:2+N+M]

    T.sort()
    out = []
    for s in S:
        out.append(str(bisect_right(T, s)))
    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

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