概要

各クエストが「効率の良いクエスト」の条件を満たすかを判定し、条件を満たすクエストの経験値を合計して目標値以上かを確認する問題です。

考察

この問題で重要なポイントは以下の通りです。

効率の良いクエストの条件

クエスト \(i\) が効率の良いクエストであるとは、獲得経験値 \(R_i\) が消費スタミナ \(D_i\) の \(K\) 倍以上であること、つまり： $\(R_i \geq K \times D_i\)$ を満たすことです。

具体例で理解する

例えば \(K = 3\) のとき：

• クエストA: \(D = 10\), \(R = 50\) → \(50 \geq 3 \times 10 = 30\) なので効率が良い ✓
• クエストB: \(D = 20\), \(R = 40\) → \(40 \geq 3 \times 20 = 60\) ではないので効率が悪い ✗

この問題のシンプルさ

この問題は複雑なアルゴリズムを必要としません。各クエストについて条件を判定し、条件を満たすものの経験値を足し合わせるだけです。

ただし注意点として、\(T\) が最大 \(10^{18}\) と非常に大きく、また \(R_i\) が最大 \(10^9\) で \(N\) が最大 \(2 \times 10^5\) なので、経験値の合計は最大で約 \(2 \times 10^{14}\) 程度になります。Python では整数のオーバーフローを気にする必要がないため、この点は問題になりません。

アルゴリズム

1. \(N\), \(K\), \(T\) を読み込む
2. 経験値の合計を保持する変数 total_exp を \(0\) で初期化
3. 各クエスト \(i\) について：
   • \(D_i\) と \(R_i\) を読み込む
   • \(R_i \geq K \times D_i\) を満たすなら、total_exp に \(R_i\) を加算
4. 最終的に total_exp >= T なら Yes、そうでなければ No を出力

total_exp = 0
for each quest i:
    if R[i] >= K * D[i]:
        total_exp += R[i]

if total_exp >= T:
    output "Yes"
else:
    output "No"

計算量

• 時間計算量: \(O(N)\)
  • 各クエストについて定数時間の判定と加算を行うため
• 空間計算量: \(O(1)\)
  • 経験値の合計を保持する変数のみを使用し、全クエストの情報を保存する必要がない

実装のポイント

1. オーバーフローへの注意（他言語の場合）: C++ などの言語では、\(K \times D_i\) の計算や経験値の合計がオーバーフローする可能性があるため、適切な型（long long など）を使用する必要があります。Python では整数型に上限がないため、この心配はありません。

2. 入力の効率的な処理: クエストの情報を配列に保存せず、読み込みながら判定・加算することで、空間計算量を \(O(1)\) に抑えています。

3. 条件式の書き方: \(R_i \geq K \times D_i\) を R >= K * D とそのまま書けば OK です。割り算を使う R / D >= K のような書き方は、浮動小数点の誤差が発生する可能性があるため避けましょう。

   ソースコード

def main():
    N, K, T = map(int, input().split())
    
    total_exp = 0
    for _ in range(N):
        D, R = map(int, input().split())
        # 効率の良いクエスト: R >= K * D
        if R >= K * D:
            total_exp += R
    
    if total_exp >= T:
        print("Yes")
    else:
        print("No")

if __name__ == "__main__":
    main()

---

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