概要

本の読んだ回数が \(K\) 回以下のものについて、その満足度の合計を求めます。

考察

この問題では、各本に対して「読んだ回数 \(C_i\)」と「満足度 \(D_i\)」が与えられます。高橋君は読んだ回数が \(K\) 回以下の本だけを読み直す候補とし、それらの満足度の合計を知りたいと考えています。

素朴な方法としては、すべての本について \(C_i \leq K\) かどうかをチェックし、条件を満たすものの \(D_i\) を合計していく方法があります。この方法は特に難しい処理を必要とせず、一度の走査で答えを得ることができます。

制約を見ると、\(N\) が最大 \(2 \times 10^5\) であり、各要素を一度ずつ見る程度であれば十分高速に動作します。また、答えが \(2 \times 10^{14}\) 以下であることが保証されているので、64ビット整数型で扱える範囲内です。

したがって、特別なアルゴリズムやデータ構造は必要なく、単純に全探索すれば良いです。

アルゴリズム

1. 入力から \(N\) と \(K\) を受け取る。
2. 満足度の合計を保持する変数 total_satisfaction を \(0\) で初期化する。
3. 各本について以下を行う：
   • \(C_i\) と \(D_i\) を入力から受け取る。
   • もし \(C_i \leq K\) なら、total_satisfaction に \(D_i\) を加算する。
4. 最終的な total_satisfaction の値を出力する。

この方法により、条件を満たす本の満足度だけを足し合わせることができ、目的の合計値を得られます。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\)

各本に対して定数時間の操作を行うため、全体では \(N\) に比例した時間で処理が完了します。また、使用するメモリも入力以外は定数サイズなので、空間計算量は \(O(1)\) です。

実装のポイント

• 条件分岐 if C <= K: の部分で、境界値（例えば \(C = K\)）が含まれることを確認しましょう。

• 満足度の合計は最大で \(2 \times 10^{14}\) になり得るので、Pythonのような言語では問題ありませんが、C++などでは long long 型などの大きな整数型を使う必要があります。

  ソースコード

# 入力の受け取り
N, K = map(int, input().split())
total_satisfaction = 0

# 各本について処理
for _ in range(N):
    C, D = map(int, input().split())
    if C <= K:
        total_satisfaction += D

# 結果の出力
print(total_satisfaction)

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