図書館の \(M\) 冊の本はすべて最低学習レベル順にしてしまっても答えは変わりません。簡単のため、最低学習レベル順に本が並んでいるとします。つまり、\(T_1 \leq T_2 \leq \ldots \leq T_M\) とします。

ここで、各 \(i\) について、 \(S_i \geq T_j\) を満たす最大の \(j\) がこの問題の答えとなります。

これは \(T\) に対して二分探索することで各 \(i\) について時間計算量 \(\mathrm{O}(\log M)\) で求まります。例えば、C++では std::upper_bound を用いて \(T_j >S_i\) を満たす最小の \(j\) が求まり、\(j-1\) が \(i\) についての答えとなります。

よって、全体で時間計算量 \(\mathrm{O}((N+M)\log M)\) で解くことができます。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    vector<int> s(n), t(m);
    for (auto& e : s) cin >> e;
    for (auto& e : t) cin >> e;
    sort(t.begin(), t.end());
    for (int i = 0; i < n; ++i) {
        auto it = upper_bound(t.begin(), t.end(), s[i]);
        cout << it - t.begin() << endl;
    }
}