概要

\(N\) 冊の本の中から、読んだ回数 \(C_i\) が指定された上限 \(K\) 以下である本をすべて選び、それらの満足度 \(D_i\) の合計を求める問題です。

考察

この問題で求められているのは、「条件を満たす要素の抽出と合計」という非常にシンプルな操作です。

1. 条件の判定: 各本について、「読んだ回数 \(C_i\) が \(K\) 以下であるか（\(C_i \leq K\)）」を判定します。
2. 合計の計算: 条件を満たす場合のみ、その本の満足度 \(D_i\) を合計値に加算します。
3. 制約の確認:
   • 本の数 \(N\) は最大 \(2 \times 10^5\) です。1冊ずつ順番に確認していけば、全体で \(2 \times 10^5\) 回程度の計算で済むため、制限時間内に十分間に合います。
   • 読んだ回数 \(C_i\) や上限 \(K\) は最大 \(10^9\) と大きいですが、これらは単に大小比較に使うだけなので、値の大きさ自体は計算速度に影響しません。
   • 満足度の合計は最大 \(2 \times 10^{14}\) に達しますが、Pythonの整数型（int）は上限なく大きな値を扱えるため、オーバーフロー（桁あふれ）を心配する必要はありません。

以上のことから、全てのデータを1回ずつ確認する「線形走査」のアプローチで解くことができます。

アルゴリズム

1. 合計満足度を格納する変数 total_satisfaction を \(0\) で初期化します。
2. \(N\) 冊の本について、以下の処理を繰り返します。
   • 本のデータ \((C_i, D_i)\) を読み込む。
   • もし \(C_i \leq K\) ならば、total_satisfaction に \(D_i\) を加える。
3. 最終的な total_satisfaction の値を出力します。

計算量

• 時間計算量: \(O(N)\)
  • 本の数 \(N\) に対して、各本を1回ずつ確認するため、処理時間は \(N\) に比例します。
• 空間計算量: \(O(N)\)
  • 今回のコードでは sys.stdin.read().split() を使用して入力データを一度に全てメモリに読み込んでいるため、入力サイズに比例したメモリを消費します。

実装のポイント

• 高速な入出力: Pythonで入力の数（\(N\)）が多い場合、input() を繰り返すと実行時間が長くなることがあります。sys.stdin.read().split() を使って一括で読み込み、イテレータ（map(int, ...)）で処理することで、効率的にデータを読み込むことができます。

• 条件分岐: 「該当する本が1冊もない場合」という条件がありますが、初期値を \(0\) にしておき、条件を満たすときだけ加算するようにすれば、特別な処理を書かなくても自動的に \(0\) が出力されます。

  ソースコード

import sys

def solve():
    # 標準入力から全てのデータを取得し、スペースや改行で分割する
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # データを整数に変換するイテレータを作成
    it = map(int, input_data)
    
    # N（本の数）とK（読んだ回数の上限）を取得
    try:
        n = next(it)
        k = next(it)
    except StopIteration:
        return
    
    total_satisfaction = 0
    # 各本の「読んだ回数C」と「満足度D」を順に処理
    for _ in range(n):
        try:
            c = next(it)
            d = next(it)
            # 読んだ回数がK以下であれば満足度を加算
            if c <= k:
                total_satisfaction += d
        except StopIteration:
            break
            
    # 結果を出力
    print(total_satisfaction)

if __name__ == '__main__':
    solve()

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