概要

\(N\) 人の生徒に、それぞれの読解力 \(T_j\) 以下の難易度 \(R_i\) を持つ本の中で、最も面白さ \(S_i\) が高い本を貸し出したときの、面白さの合計を求める問題です。

考察

まず、素朴な方法を考えてみます。各生徒について、すべての本（\(M\) 冊）をチェックして「難易度が \(T_j\) 以下」かつ「面白さが最大」の本を探すと、計算量は \(O(N \times M)\) となります。 本問題の制約では \(N, M \leq 2 \times 10^5\) であるため、最大で \(4 \times 10^{10}\) 回程度の計算が必要になり、実行時間制限に間に合いません。

そこで、効率的に解くための重要な性質に注目します。 「読解力が高い生徒は、読解力が低い生徒が読める本をすべて読むことができる」 という点です。

もし生徒を読解力の低い順に並べ、本を難易度の低い順に並べたとしたらどうでしょうか。 1. 読解力が一番低い生徒が読める本をすべて確認し、その中での最大値を記録します。 2. 次に読解力が少し高い生徒について考えるとき、「前の生徒が読めた本」は引き続き候補に入ります。 3. つまり、新しく候補に加わった本（難易度が前の生徒より高く、現在の生徒の読解力以下の本）だけをチェックし、これまでの最大値を更新していけばよいことになります。

このように、生徒と本をどちらも昇順にソートして順番に見ていくことで、各本を一度ずつチェックするだけで全生徒の最適な本を決定できます。

アルゴリズム

1. ソート:
   • 本を難易度 \(R_i\) の昇順にソートします。
   • 生徒を読解力 \(T_j\) の昇順にソートします。
2. 走査（ツーポインタ風の処理）:
   • 現在の生徒が読める本の面白さの最大値を保持する変数 max_fun を \(0\) で初期化します。
   • ソートした生徒を一人ずつ見ていき、以下の操作を行います。
     • まだチェックしていない本の中で、その生徒の読解力以下の難易度の本がある限り、その本の面白さで max_fun を更新し続けます。
     • その生徒にとっての最高得点は現在の max_fun なので、これを合計値に加算します。
3. 出力:
   • 全員の合計値を出力します。

計算量

• 時間計算量: \(O(M \log M + N \log N)\)
  • 本のソートに \(O(M \log M)\)、生徒のソートに \(O(N \log N)\) かかります。
  • その後の走査は、生徒の人数 \(N\) と本の冊数 \(M\) に対してそれぞれ一度ずつしか見ていかないため \(O(N + M)\) です。
• 空間計算量: \(O(N + M)\)
  • 入力データを保持するためのメモリが必要です。

実装のポイント

• 高速な入出力: \(N, M\) が大きいため、Python では sys.stdin.read().split() などを用いて一括で入力を読み込むと実行時間を短縮できます。

• 同じ本の複数貸し出し: 問題文に「同じ本は複数人に貸し出すことができる」とあるため、一度見つけた「これまでの最大値」は、より読解力が高い後続の生徒にもそのまま適用できます。本の在庫を管理する必要がないため、単純な最大値の保持だけで完結します。

  ソースコード

import sys

def solve():
    # Read all input at once for fast processing
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # Use an iterator to consume the input data
    it = iter(input_data)
    
    # Number of students and books
    N = int(next(it))
    M = int(next(it))
    
    # Store books as (difficulty, fun) tuples
    # Input order for each book is fun S_i then difficulty R_i
    books = []
    for _ in range(M):
        s = int(next(it))
        r = int(next(it))
        books.append((r, s))
        
    # Store student reading levels T_j
    students = []
    for _ in range(N):
        students.append(int(next(it)))
        
    # Sort books by difficulty (ascending)
    # If difficulties are equal, it sorts by fun (ascending)
    books.sort()
    
    # Sort students by reading level (ascending)
    students.sort()
    
    total_fun_sum = 0
    max_fun_available = 0
    book_idx = 0
    
    # Iterate through students in increasing order of reading level
    for t in students:
        # Add all books that the current student is capable of reading
        # Since students are sorted, the set of readable books for the next student
        # will always be a superset of the current student's readable books.
        while book_idx < M and books[book_idx][0] <= t:
            # Keep track of the maximum fun value encountered so far
            if books[book_idx][1] > max_fun_available:
                max_fun_available = books[book_idx][1]
            book_idx += 1
        
        # Add the maximum possible fun for this student to the total
        total_fun_sum += max_fun_available
        
    # Output the result
    sys.stdout.write(str(total_fun_sum) + '\n')

if __name__ == '__main__':
    solve()

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