概要

各生徒が読める本の中から最も面白さの高い本を選び、その面白さの合計を求める問題。

考察

この問題では、各生徒に対して「読解力 \(T_j\) 以下」という条件を満たす本の中で、最も面白さ \(S_i\) が高いものを選ぶ必要があります。
もし全探索で毎回最大値を探すと、計算量が \(O(N \times M)\) となり、制約が大きいため時間内に解けません（TLE）。

そこで、「本を難易度 \(R_i\) でソートしておけば、ある読解力 \(T_j\) に対して読める本の範囲が連続になる」ことに注目します。これにより、累積的に「難易度が \(R_i\) 以下の本の中で最大の面白さ」を前計算しておくことで、各クエリを高速に処理できます。
さらに、ソートされた配列上で「読解力以下の最大の難易度を持つ本の位置」を二分探索で求めることで、全体を高速化できます。

アルゴリズム

1. 各本を難易度 \(R_i\) の昇順にソートする。
2. ソートされた順に、各位置まででの最大面白さを累積的に記録する配列 max_interest_up_to を作る。
3. 各生徒の読解力 \(T_j\) について、難易度が \(T_j\) 以下の本のうち、最大の面白さを二分探索で求める。
4. その面白さを合計していく。

例えば、本が以下のように与えられたとします： - 本1: \((S=5, R=3)\) - 本2: \((S=7, R=1)\) - 本3: \((S=6, R=4)\)

これを難易度でソートすると： - 本2: \((S=7, R=1)\) - 本1: \((S=5, R=3)\) - 本3: \((S=6, R=4)\)

このとき、各難易度までの最大面白さは： - 難易度1まで：7 - 難易度3まで：max(7, 5) = 7 - 難易度4まで：max(7, 5, 6) = 7

よって、max_interest_up_to = [7, 7, 7] となります。
生徒の読解力が例えば 3 であれば、難易度が 3 以下の本の最大面白さは 7 です。

計算量

• 時間計算量: \(O(M \log M + N \log M)\)
  • 本のソートに \(O(M \log M)\)、各生徒について二分探索で最大面白さを取得するのに \(O(N \log M)\)
• 空間計算量: \(O(M + N)\)
  • 本のリストと累積最大面白さテーブル、生徒リストの分

実装のポイント

• 二分探索を使う際、(difficulty, infinity) のようなタプルを使って比較することで、難易度が一致する中で最後の要素を正確に探せる。
• 前計算で「難易度 \(R_i\) 以下の本の最大面白さ」を保持しておくのが肝心。
• 同じ本を複数人借りられるので、個別の管理は不要。

## ソースコード

```python
import sys
from bisect import bisect_right
import heapq

def main():
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    
    books = []
    idx = 2
    for _ in range(M):
        s = int(data[idx])
        r = int(data[idx+1])
        books.append((r, s))
        idx += 2
    
    # 難易度でソート
    books.sort()
    
    # 難易度ごとの最大面白さを計算
    max_interest_up_to = [0] * M
    max_s = 0
    for i in range(M):
        max_s = max(max_s, books[i][1])
        max_interest_up_to[i] = max_s
    
    # 生徒の読解力を読み込み
    students = list(map(int, data[idx:idx+N]))
    
    total = 0
    for t in students:
        # 読める本のうち、難易度 <= t である最大のindexを二分探索
        pos = bisect_right(books, (t, float('inf'))) - 1
        if pos >= 0:
            total += max_interest_up_to[pos]
    
    print(total)

if __name__ == "__main__":
    main()

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