概要

与えられた \(N\) 個のクエストの中から、獲得経験値 \(R_i\) が消費スタミナ \(D_i\) の \(K\) 倍以上であるものだけを選び出し、その経験値の合計が目標値 \(T\) 以上になるかを判定する問題です。

考察

この問題で重要な点は、「どのクエストをクリアすべきか」の判断基準が独立していることです。

各クエストについて、条件 \(R_i \geq K \times D_i\) を満たしているかどうかを個別に判定すればよく、他のクエストの選択状況が影響することはありません。したがって、以下の手順で解くことができます。

1. 合計経験値を保持する変数を用意する。
2. \(N\) 個のクエストを 1 つずつ順番に確認する。
3. 条件を満たすクエストであれば、その経験値を合計に加算する。
4. 最後に合計が \(T\) 以上かを確認する。

注意点として、目標経験値 \(T\) は最大で \(10^{18}\) という非常に大きな値になります。プログラミング言語によっては 64 ビット整数型（C++ の long long など）を使用する必要がありますが、Python では標準の整数型でこの大きさを扱うことができるため、オーバーフローの心配はありません。

アルゴリズム

以下の手順で実装します。

1. 入力から \(N, K, T\) を受け取る。
2. 合計経験値を格納する変数 total_experience を \(0\) で初期化する。
3. \(N\) 回のループを回し、各クエストの \(D_i, R_i\) を読み込む。
4. if r >= k * d: という条件式で効率が良いかを判定する。
5. 条件を満たす場合、total_experience に \(R_i\) を加算する。
6. ループ終了後、total_experience >= t であれば Yes、そうでなければ No を出力する。

計算量

• 時間計算量: \(O(N)\)
  • クエストの数 \(N\) に対して 1 回ずつループを回して判定を行うため、線形時間で処理が終わります。\(N = 2 \times 10^5\) であっても十分に高速です。
• 空間計算量: \(O(N)\)
  • 与えられたコードでは sys.stdin.read().split() を使用して全ての入力を一度にリストとして読み込んでいるため、入力サイズに比例したメモリを消費します。

実装のポイント

• 高速な入出力: \(N\) が最大 \(2 \times 10^5\) と比較的大きいため、input() を繰り返すよりも sys.stdin.read().split() や sys.stdin.readline を使用することで、実行時間を短縮できます。

• 条件式の記述: 問題文の通り \(R_i \geq K \times D_i\) をそのままコードに落とし込むことで、浮動小数点数（割り算）を使わずに整数のみで正確に判定できます。

  ソースコード

import sys

def solve():
    # 標準入力からすべてのデータを取得し、スペース・改行で分割する
    data = sys.stdin.read().split()
    if not data:
        return
    
    # イテレータを使用してデータを順番に処理する
    it = iter(data)
    
    # N: クエスト数, K: 効率の基準, T: 目標経験値
    try:
        n_str = next(it)
        k_str = next(it)
        t_str = next(it)
    except StopIteration:
        return

    n = int(n_str)
    k = int(k_str)
    t = int(t_str)
    
    total_experience = 0
    
    # 各クエストの情報を処理
    for _ in range(n):
        try:
            d = int(next(it))
            r = int(next(it))
            
            # 効率の良いクエスト（Ri >= K * Di）のみ経験値を加算
            if r >= k * d:
                total_experience += r
        except StopIteration:
            break
            
    # 合計経験値が目標 T 以上かどうかを判定
    if total_experience >= t:
        print("Yes")
    else:
        print("No")

if __name__ == '__main__':
    solve()

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