概要

各生徒に対して「読める本（難易度が読解力以下）の中で最も面白い本」を貸し出し、面白さの合計を求める問題です。同じ本を複数人に貸せるため、各生徒を独立に考えることができます。

考察

重要な気づき

同じ本を何人にでも貸し出せるので、生徒同士で本の取り合いは起きません。つまり、各生徒について独立に「難易度 \(R_i \leq T_j\) を満たす本の中での面白さの最大値」を求めればよいということになります。

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

各生徒 \(j\) に対して、\(M\) 冊すべてを調べて \(R_i \leq T_j\) かつ \(S_i\) が最大のものを探すと、計算量は \(O(N \times M)\) になります。\(N, M\) がそれぞれ最大 \(2 \times 10^5\) なので、最悪 \(4 \times 10^{10}\) 回の操作が必要となり、制限時間に間に合いません。

解決のアイデア

本を難易度の昇順にソートしておき、前からの面白さの累積最大値（prefix max）を計算しておきます。

例えば、本が難易度順に並んでいるとき：

本	難易度 \(R\)	面白さ \(S\)	prefix max
A	2	5	5
B	3	8	8
C	5	3	8
D	7	10	10

生徒の読解力が \(T_j = 4\) の場合、難易度 \(4\) 以下の本は A, B, C です。その中の面白さの最大値は prefix max から \(8\) と即座にわかります。

「難易度 \(\leq T_j\) を満たす最後の本の位置」は、ソート済み配列に対する二分探索で高速に求められます。

アルゴリズム

1. \(M\) 冊の本を難易度 \(R_i\) の昇順にソートする。
2. ソートした順に面白さの累積最大値（prefix max）を計算する。
   • prefix_max[k] = ソート後の先頭 \(k+1\) 冊の中での \(S_i\) の最大値
3. 各生徒 \(j\) について：
   • 二分探索（bisect_right）で、難易度配列の中から \(T_j\) 以下の最後の位置 pos を求める。
   • pos >= 0 なら prefix_max[pos] を合計に加算する（読める本がある場合）。
   • pos < 0 なら読める本がないので \(0\) を加算する。
4. 合計を出力する。

計算量

• 時間計算量: \(O(M \log M + N \log M)\)
  • 本のソートに \(O(M \log M)\)
  • 各生徒について二分探索に \(O(\log M)\)、それが \(N\) 人分で \(O(N \log M)\)
• 空間計算量: \(O(N + M)\)
  • 本の情報、prefix max 配列、生徒の読解力配列の格納

実装のポイント

• bisect_right の使い方: bisect_right(difficulties, t) は「\(t\) より大きい最初の位置」を返すので、そこから \(1\) 引くと「\(t\) 以下の最後の位置」になります。結果が \(-1\)（= 読める本がない）の場合の処理を忘れないようにします。

• 入力の高速化: \(N, M\) が大きいため、sys.stdin.buffer.read() でまとめて読み込むことで入出力を高速化しています。

• prefix max の構築: ソート後に1回のループで構築でき、各クエリへの応答を \(O(1)\)（二分探索部分を除く）にできます。

  ソースコード

import sys
from bisect import bisect_right

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    books = []
    for i in range(M):
        s = int(input_data[idx]); idx += 1
        r = int(input_data[idx]); idx += 1
        books.append((r, s))
    
    T = [int(input_data[idx + j]) for j in range(N)]
    idx += N
    
    # Sort books by difficulty
    books.sort()
    
    # Build prefix max of fun values sorted by difficulty
    # For each difficulty threshold, the best fun is the max fun among all books with r <= threshold
    difficulties = []
    prefix_max = []
    current_max = 0
    for r, s in books:
        current_max = max(current_max, s)
        difficulties.append(r)
        prefix_max.append(current_max)
    
    total = 0
    for t in T:
        # Find rightmost book with difficulty <= t
        pos = bisect_right(difficulties, t) - 1
        if pos >= 0:
            total += prefix_max[pos]
    
    print(total)

main()

---

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