概要

この問題は、毎ターン利息によって膨らんでいく \(N\) 件の借金を、毎ターン得られる固定の予算 \(P\) 円を使ってすべて完済できるかを判定する問題です。各借金には「何ターン目までに返済しなければならないか」という明確な返済期限（締め切り）が存在するため、これを求めて貪欲法（締め切りが早い順に処理する手法）を適用することで解決できます。

---

考察

1. 各借金の「返済期限」を考える

ある借金 \(i\) について、第 \(t\) ターン（\(t \geq 1\)）の返済フェーズにおける残高は、初期残高 \(H_i\) に \(t-1\) 回分の利息 \(G_i\) が加算された額になります。すなわち、残高は以下の式で表されます。

\[H_i + (t - 1) \times G_i\]

この借金を第 \(t\) ターンに完済するためには、この時点での残高が \(P\) 以下である必要があります。

\[H_i + (t - 1) \times G_i \leq P\]

この不等式を \(t\) について解いてみましょう。

\[(t - 1) \times G_i \leq P - H_i\]

\[t - 1 \leq \frac{P - H_i}{G_i}\]

\[t \leq \frac{P - H_i}{G_i} + 1\]

\(t\) は整数であるため、借金 \(i\) を完済できる最大のターン数 \(T_i\) は、切り捨て除算（\(\lfloor \rfloor\)）を用いて以下のように表せます。

\[T_i = \lfloor \frac{P - H_i}{G_i} \rfloor + 1\]

ただし、そもそも初期残高が予算を超えている（\(P < H_i\)）場合は、第 \(1\) ターンであっても返済できません。この場合の返済期限は \(0\) ターン目（＝返済不可能）とします。

2. どの順番で返済すべきか？

すべての借金の返済期限 \(T_i\) が求まったら、次に関門となるのは「1ターンに最大1件しか返済できない」という制約です。

これはタスクスケジューリングの典型問題であり、「締め切り（返済期限）が早いものから順に処理する」という貪欲法が最適になります。締め切りが遅いものを後回しにし、猶予がないものから優先的に片付けていくのが最も効率的だからです。

3. 完済可能かどうかの判定

すべての借金の返済期限を昇順（小さい順）にソートしたリストを \(L\) とします。 ソート後の \(j\) 番目（0-indexed、すなわち \(0 \leq j < N\)）の借金は、少なくとも \(j + 1\) ターン目までに返済しなければなりません。なぜなら、それより前の借金を返済するのに最低でも \(j\) ターン消費しているからです。

したがって、すべての \(j\) について以下の条件が成り立っていれば、すべての借金を完済できます。

\[L[j] \geq j + 1\]

逆に、一つでも \(L[j] < j + 1\) となる \(j\) が存在する場合、その借金の締め切りまでに返済が間に合わないため、答えは No となります。

---

アルゴリズム

1. 各借金 \(i\) （\(1 \leq i \leq N\)）について、返済期限 \(T_i\) を計算し、リスト L に追加します。
   • \(P < H_i\) のとき： \(T_i = 0\)
   • \(P \geq H_i\) のとき： \(T_i = (P - H_i) // G_i + 1\) （// は切り捨て除算）
2. リスト L を昇順にソートします。
3. 各 \(j\) （\(0 \leq j < N\)）について、L[j] < j + 1 であるかを判定します。
   • もし満たすものがあれば、その時点で No を出力して終了します。
4. すべての要素で条件をクリアした場合、Yes を出力します。

---

計算量

• 時間計算量: \(O(N \log N)\) 各借金の返済期限の計算に \(O(N)\)、リストのソートに \(O(N \log N)\)、最後の判定ループに \(O(N)\) かかります。全体のボトルネックはソート部分であり、制約の \(N \leq 2 \times 10^5\) に対しても十分高速（数ミリ秒〜数十ミリ秒）に動作します。

• 空間計算量: \(O(N)\) 各借金の返済期限を格納するリスト L のために \(O(N)\) のメモリを使用します。

---

実装のポイント

• 切り捨て除算の扱い: Pythonでは // 演算子を使用することで、自動的に小数点以下を切り捨てた整数（床関数 \(\lfloor \rfloor\)）を求めることができます。

• インデックスの対応: プログラミング言語の配列は通常 0 から始まる（0-indexed）ため、ソート後の \(j\) 番目の要素（\(0\)-indexed）に対する期限のチェックは j + 1 ターン目との比較になります。このズレに注意しましょう。

  ソースコード

import sys


def solve():
    # 高速な入力処理
    input = sys.stdin.read
    data = input().split()
    if not data:
        return

    N = int(data[0])
    P = int(data[1])

    L = []
    idx = 2
    for _ in range(N):
        H = int(data[idx])
        G = int(data[idx + 1])
        idx += 2
        if P < H:
            L.append(0)
        else:
            L.append((P - H) // G + 1)

    # 昇順にソート
    L.sort()

    # 各jに対して、L[j]がj+1以上であるか確認
    for j in range(N):
        if L[j] < j + 1:
            print("No")
            return

    print("Yes")


if __name__ == "__main__":
    solve()

---

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