概要

各クエストの消費スタミナと獲得経験値から、「効率の良いクエスト」（獲得経験値 \(\geq K \times\) 消費スタミナ）を選び、その経験値の合計が目標値 \(T\) 以上になるかを判定する問題。

考察

この問題では、各クエストについて「効率が良いかどうか」を個別に判定し、効率の良いクエストの経験値をすべて足し合わせる必要があります。

重要な観察点は、効率の良いクエストとは「\(R_i \geq K \times D_i\)」を満たすクエストであるということです。これは単純な比較であり、ソートや複雑な前処理は必要ありません。

素朴なアプローチとして、すべてのクエストに対して条件を確認し、該当すれば経験値を加算していく方法があります。この方法は各クエストにつき定数時間で判定できるので、十分高速です。

逆に、もしクエスト数 \(N\) が非常に大きい場合（例えば \(10^6\) 以上）であれば、より高度なアルゴリズムが必要になるかもしれませんが、この問題では \(N \leq 2 \times 10^5\) なので全探索でも間に合います。

また、経験値の合計値は最大で \(10^9 \times 2 \times 10^5 = 2 \times 10^{14}\) 程度になりうるので、32bit整数型ではなく64bit整数型（Pythonでは標準のint）を使う必要があります。

アルゴリズム

1. 各クエスト \((D_i, R_i)\) に対して、\(R_i \geq K \times D_i\) かどうかを判定する。
2. 条件を満たすクエストの経験値 \(R_i\) を合計していく。
3. 最終的な合計値が \(T\) 以上であれば Yes、そうでなければ No を出力する。

たとえば、以下のような入力の場合：

3 2 10
2 5
3 6
1 3

• クエスト1: \(5 \geq 2 \times 2 = 4\) → OK
• クエスト2: \(6 \geq 2 \times 3 = 6\) → OK
• クエスト3: \(3 \geq 2 \times 1 = 2\) → OK

合計経験値 = \(5 + 6 + 3 = 14 \geq 10\) → 出力は Yes

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\)（入力を除く）

各クエストに対して定数時間の判定を行うため、全体で線形時間となります。また、合計値を保持する変数ひとつだけで済むため、追加のメモリ使用量は定数です。

実装のポイント

• 入力を受け取る際に、各クエストの \((D_i, R_i)\) をタプルやリストでまとめて管理するとコードが整理しやすい。

• 合計値は64bit整数型で扱うこと（Pythonの int は自動的に対応している）。

• 条件判定は不等号を正しく記述すること（\(R_i \geq K \times D_i\)）。

  ソースコード

# 入力の受け取り
N, K, T = map(int, input().split())
quests = [tuple(map(int, input().split())) for _ in range(N)]

# 効率の良いクエストの経験値合計を計算
total_exp = 0
for D, R in quests:
    if R >= K * D:
        total_exp += R

# 目標達成可否の判定と出力
if total_exp >= T:
    print("Yes")
else:
    print("No")

---

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