概要

\(N\) 冊の本の中から、読んだ回数が \(K\) 回以下の本を全て選び、それらの満足度の合計を求める問題です。

考察

この問題は非常にシンプルで、各本について「読んだ回数が \(K\) 回以下かどうか」を判定し、条件を満たす本の満足度を足し合わせるだけです。

重要な気づき

• 各本は独立して判定できる（他の本の情報は不要）
• 条件 \(C_i \leq K\) を満たすかどうかを1冊ずつチェックすれば良い
• ソートや複雑なデータ構造は不要

具体例で考える

例えば、\(N = 3\)、\(K = 2\) で以下の本があるとします： - 本1: 読んだ回数 \(C_1 = 1\)、満足度 \(D_1 = 100\) - 本2: 読んだ回数 \(C_2 = 3\)、満足度 \(D_2 = 200\) - 本3: 読んだ回数 \(C_3 = 2\)、満足度 \(D_3 = 150\)

\(K = 2\) 回以下の本は、本1（1回）と本3（2回）です。 よって、答えは \(100 + 150 = 250\) となります。

なぜこの単純な方法で十分か

• \(N \leq 2 \times 10^5\) なので、全ての本を1回ずつ見ても十分高速
• 各本の判定は定数時間 \(O(1)\) で可能
• 特別な最適化は必要ない

アルゴリズム

1. 満足度の合計を保持する変数 total を \(0\) で初期化する
2. \(N\) 冊の本について、1冊ずつ以下を行う：
   • その本の読んだ回数 \(C_i\) と満足度 \(D_i\) を読み込む
   • \(C_i \leq K\) ならば、total に \(D_i\) を加算する
3. 最終的な total を出力する

計算量

• 時間計算量: \(O(N)\)
  • \(N\) 冊の本それぞれについて、条件判定と加算を1回ずつ行う
• 空間計算量: \(O(1)\)
  • 合計値を保持する変数のみを使用し、本の情報を全て保存する必要はない

実装のポイント

• オーバーフローに注意: 満足度の最大値は \(10^9\)、本の冊数は最大 \(2 \times 10^5\) なので、合計は最大で \(2 \times 10^{14}\) 程度になります。Python では整数のオーバーフローを気にする必要はありませんが、C++ などでは long long 型を使う必要があります。

• 該当する本がない場合: 初期値を \(0\) にしておけば、条件を満たす本が1冊もなくても自然に \(0\) が出力されます。

• メモリ効率: 全ての本の情報を配列に保存せず、読み込みながら即座に判定・加算することで、空間計算量を \(O(1)\) に抑えています。

  ソースコード

N, K = map(int, input().split())
total = 0
for _ in range(N):
    C, D = map(int, input().split())
    if C <= K:
        total += D
print(total)

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