概要

各学生が何冊の本を借りられるかを、学年制限に基づいて求める問題。

考察

この問題では、各学生 \(i\) に対して、条件 \(S_i \geq T_j\) を満たす本 \(j\) の数を数える必要があります。

素朴な解法として、全ての学生と全ての本の組み合わせを調べる方法（二重ループ）が考えられますが、これは最大で \(2 \times 10^5 \times 2 \times 10^5 = 4 \times 10^{10}\) 回の比較が必要となり、時間制限を超えてしまいます（TLE）。

そこで、効率的に処理するために以下のような観察を行います： - 各学生の借りられる本の冊数は、「\(T_j \leq S_i\) であるような \(T_j\) の個数」に等しい。 - よって、もし本の必要学年リスト \(T\) がソートされていれば、二分探索によって「\(S_i\) 以下であるような \(T_j\) の最大のindex」を高速に求めることができます。

具体的に、例えば
\(S_i = 5\),
\(T = [1, 2, 4, 6, 7]\)
であれば、\(S_i\) 以上の最小の \(T_j\) ではなく、「\(S_i\) 以下の最大のindex」を探すのがポイントです。
つまり、bisect.bisect_right(T, s) を使うことで、\(s\) より大きい最初の位置を得ることができ、そのindexがそのまま借りられる本の冊数になります。

このように、事前に \(T\) をソートしておけば、各クエリを \(O(\log M)\) で処理できます。

アルゴリズム

1. 入力を読み込み、本の必要学年リスト \(T\) をソートする。
2. 各学生の学年 \(S_i\) について、\(T\) 上で \(S_i\) 以下の要素の個数を二分探索で求める。
   • Pythonの bisect.bisect_right(T, s) を使うと、\(s\) より大きい最初のindexが得られるため、それがそのまま借りられる本の冊数となる。
3. 結果を順に出力する。

計算量

• 時間計算量: \(O(M \log M + N \log M)\)
  
  • \(T\) のソートに \(O(M \log M)\)、各学生に対する二分探索に \(O(N \log M)\)
• 空間計算量: \(O(N + M)\)
  
  • 学生と本の情報を格納する配列分

実装のポイント

• bisect.bisect_right は「指定した値より大きい最初のindex」を返すので、このまま借りられる本の冊数に対応します。
• 最初に \(T\) をソートすることを忘れずに。

## ソースコード

```python
import bisect

# 入力受け取り
N, M = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))

# Tをソート
T.sort()

# 各学生に対して、借りられる本の冊数を二分探索で求める
result = []
for s in S:
    # Tの中で s 以上となる最初の位置を二分探索で求める
    pos = bisect.bisect_right(T, s)
    result.append(pos)

# 結果出力
print(*result, sep='\n')

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