概要

各生徒の読解力以下の難易度を持つ本の中で最も面白い本を選び、その面白さの合計を求める問題です。

考察

素朴なアプローチとして、各生徒に対して全ての本をチェックし、読める本の中で最大の面白さを見つける方法が考えられます。しかし、\(N\) と \(M\) が最大 \(2 \times 10^5\) ずつあるため、\(O(NM)\) の計算量では時間制限に間に合いません。

効率的に解くためには、以下の2つの観察が必要です： 1. 本を難易度でソートし、各難易度以下で利用可能な最大の面白さを事前計算する 2. 各生徒の読解力に対して、二分探索で適切な本の範囲を特定する

アルゴリズム

1. 本の前処理:

   • 本を難易度 \(R_i\) の昇順にソートする
   • ソートされた本を順に見ていき、各難易度までで達成可能な最大の面白さを記録する（累積最大）

2. 生徒への対応:

   • 各生徒の読解力 \(T_j\) に対して、二分探索（bisect_right）でその読解力以下で読める本の範囲を特定する
   • 事前計算した累積最大の面白さから、その範囲内での最大面白さを取得する
   • 該当する本があればその面白さを合計に加算する

計算量

• 時間計算量: \(O((N + M) \log M)\)
  • 本のソート: \(O(M \log M)\)
  • 累積最大の計算: \(O(M)\)
  • 各生徒の二分探索: \(O(N \log M)\)
• 空間計算量: \(O(M)\)
  • 本の情報を格納するための配列

実装のポイント

• 本を（難易度, 面白さ）のタプルで管理し、難易度でソート

• bisect_right を使用して、生徒の読解力以下の最大の難易度位置を特定

• 累積最大の面白さを格納する配列を別途用意し、効率的に最大値を取得できるようにする

• 読める本がない場合（位置が0）は合計に加算しないように注意

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        print(0)
        return
        
    n = int(data[0])
    m = int(data[1])
    
    books = []
    index = 2
    for i in range(m):
        s = int(data[index])
        r = int(data[index+1])
        index += 2
        books.append((r, s))
    
    students = list(map(int, data[index:index+n]))
    
    books.sort(key=lambda x: x[0])
    
    max_s = 0
    best_books = []
    for r, s in books:
        if s > max_s:
            max_s = s
        best_books.append((r, max_s))
    
    from bisect import bisect_right
    
    best_books_r = [book[0] for book in best_books]
    best_books_s = [book[1] for book in best_books]
    
    total = 0
    for t in students:
        pos = bisect_right(best_books_r, t)
        if pos > 0:
            total += best_books_s[pos-1]
    
    print(total)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。