概要

この問題は、\(N\) 人の利用者のそれぞれについて、与えられた \(M\) 冊の本の中から「難易度が自分の読解力以下である本」が何冊あるかを求める問題です。

考察

素朴なアプローチ

まず、各利用者ごとにすべての本をチェックする方法を考えてみます。 1. 利用者 1 について、本 1 から本 \(M\) までを確認し、読める本の冊数を数える。 2. 利用者 2 についても同様に、本 1 から本 \(M\) までを確認する。 3. これを \(N\) 人分繰り返す。

この方法（二重ループ）では、計算回数が \(N \times M\) 回となります。制約を見ると \(N, M \leq 2 \times 10^5\) なので、最大で \(4 \times 10^{10}\) 回程度の計算が必要になり、実行時間制限（通常 2 秒程度）に間に合いません。

効率的なアプローチ

「ある値 \(S_j\) 以下の要素が何個あるか」を高速に求めるには、二分探索が非常に有効です。 本の難易度リスト \(D\) をあらかじめ昇順（小さい順）に並べ替えておくと、読解力 \(S_j\) に対して「どこまでの本が読めるか」を高速に見つけることができます。

例えば、本の難易度が \(D = [10, 20, 30, 40, 50]\) とソートされており、利用者の読解力が \(S_j = 35\) の場合、二分探索を用いると「30 と 40 の間」が境界であることをすぐに見つけられ、読める本が 3 冊（10, 20, 30）であると分かります。

アルゴリズム

1. 本の難易度のソート: 本の難易度のリスト \(D\) を昇順にソートします。
2. 二分探索の実行: 各利用者の読解力 \(S_j\) について、ソートされたリスト \(D\) に対して二分探索を行います。具体的には、 Python の bisect_right 関数などを用いて、「\(S_j\) 以下の値がリストの何番目まで続くか」を取得します。
3. 結果の出力: 求まった冊数を各利用者ごとに順に出力します。

計算量

• 時間計算量: \(O((N + M) \log M)\)
  • 本のソートに \(O(M \log M)\) かかります。
  • 各利用者の二分探索に \(O(\log M)\) かかり、それが \(N\) 人分あるため \(O(N \log M)\) です。
  • \(N, M = 2 \times 10^5\) のとき、全体で約 \(10^7\) 回程度の計算量となり、制限時間内に十分間に合います。
• 空間計算量: \(O(N + M)\)
  • 本の難易度と利用者の読解力を保持するためにリストを使用します。

実装のポイント

• 高速な入出力: \(N\) や \(M\) が大きいため、Python の標準的な input() や print() を繰り返すと入出力がボトルネックになる可能性があります。sys.stdin.read().split() で一括で読み込み、sys.stdout.write() で一括で出力することで高速化を図っています。

• bisectモジュールの活用: Python の標準ライブラリである bisect モジュールを使うことで、二分探索を簡潔かつ高速に実装できます。bisect_right(D, s) は、リスト \(D\) に値 \(s\) を挿入できる最も右側のインデックスを返します。これは「\(s\) 以下の要素の個数」と一致します。

  ソースコード

import sys
import bisect

def solve():
    # 入力をすべて読み込み、スペースや改行で分割してリストにする
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 利用者の人数, M: 本の冊数
    N = int(input_data[0])
    M = int(input_data[1])
    
    # D: 各本の難易度 (インデックス 2 から 2+M-1 まで)
    D = list(map(int, input_data[2:2+M]))
    
    # S: 各利用者の読解力 (インデックス 2+M から 2+M+N-1 まで)
    S = list(map(int, input_data[2+M:2+M+N]))
    
    # 本の難易度を昇順にソートする
    # これにより二分探索が可能になる
    D.sort()
    
    # 各利用者の読解力 S_j に対して、D_i <= S_j を満たす本の冊数を二分探索で求める
    # bisect_right は、ソートされたリストに対して指定した値以下の要素が何個あるかを O(log M) で返す
    results = []
    for s in S:
        count = bisect.bisect_right(D, s)
        results.append(str(count))
    
    # 結果を改行区切りで一気に出力する
    sys.stdout.write('\n'.join(results) + '\n')

if __name__ == '__main__':
    solve()

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