概要

\(N\) 件の借金それぞれに「返済可能な最終ターン（締切）」が存在するため、全借金を締切内にスケジューリングできるかを判定する問題です。

考察

ターンと残高の関係

ターンを \(0\)-indexed で考えます。ターン \(t\) の返済フェーズ開始時点で、借金 \(i\) の残高は：

\[H_i + t \cdot G_i\]

です（ターン \(0\) で \(H_i\)、ターン \(1\) で \(H_i + G_i\)、…と増えていく）。

各借金の「締切」を求める

借金 \(i\) をターン \(t\) に返済できる条件は \(H_i + t \cdot G_i \leq P\) です。これを変形すると：

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

つまり、借金 \(i\) を返済できる最後のターン（締切）は \(T_i = \lfloor (P - H_i) / G_i \rfloor\) です。

• もし \(H_i > P\) なら、ターン \(0\) の時点で既に返済不可能（残高は増え続けるだけ）なので即 No。

スケジューリング問題への帰着

各ターンに返済できるのは最大 \(1\) 件で、各借金 \(i\) は ターン \(0, 1, \ldots, T_i\) のいずれかで返済する必要があります。

これは 「\(N\) 個のジョブにそれぞれ締切 \(T_i\) があり、各時刻に \(1\) 個ずつ処理するとき、全ジョブを締切内に完了できるか？」 という古典的なスケジューリング問題と同じです。

貪欲法による判定

この問題には有名な判定法があります：

締切の小さい順にソートし、\(j\) 番目（\(0\)-indexed）のジョブの締切が \(j\) 以上であれば実行可能。

直感的な理由：締切の早いものから順に、最も早い空きターンに割り当てていきます。\(j\) 番目のジョブは最善でもターン \(j\) にしか割り当てられないため、\(T_j < j\) なら不可能です。逆に全ジョブが \(T_j \geq j\) を満たせば、\(j\) 番目をターン \(j\) に割り当てる方法が常に有効です。

アルゴリズム

1. 各借金 \(i\) について、\(H_i > P\) なら No を出力して終了。
2. 締切 \(T_i = \lfloor (P - H_i) / G_i \rfloor\) を計算する。
3. \(T_i\) を昇順にソートする。
4. ソート後の配列を走査し、\(j\) 番目（\(0\)-indexed）の値が \(j\) 未満であれば No、全て通過すれば Yes。

計算量

• 時間計算量: \(O(N \log N)\)（ソートがボトルネック）
• 空間計算量: \(O(N)\)（締切配列の保持）

実装のポイント

• \(H_i \leq P\) のチェックを先に行うことで、\((P - H_i)\) が非負であることを保証してから割り算する。

• \(G_i \geq 1\) が制約で保証されているため、ゼロ除算の心配は不要。

• 値が最大 \(10^9\) 程度なのでオーバーフローの心配はないが、言語によっては注意が必要。

• 具体例：\(P = 10, H = [5, 8, 3], G = [2, 3, 4]\) のとき、締切は \(\lfloor 5/2 \rfloor = 2, \lfloor 2/3 \rfloor = 0, \lfloor 7/4 \rfloor = 1\)。ソートすると \([0, 1, 2]\)。各 \(j\) について \(T_j \geq j\)（\(0 \geq 0, 1 \geq 1, 2 \geq 2\)）なので Yes。

  ソースコード

import sys

def solve():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    P = int(input_data[idx]); idx += 1
    
    debts = []
    for i in range(N):
        H = int(input_data[idx]); idx += 1
        G = int(input_data[idx]); idx += 1
        debts.append((H, G))
    
    # At turn t (0-indexed), a debt i has balance H_i + t * G_i
    # We can pay it at turn t if H_i + t * G_i <= P, i.e., t <= (P - H_i) / G_i
    # If H_i > P and G_i > 0, we can never pay it (unless G_i = 0... but G_i >= 1)
    # Actually if H_i > P, then even at t=0, H_i + 0*G_i = H_i > P, and it only grows, so impossible.
    
    # We need to assign each debt to a distinct turn, and at that turn the balance must be <= P.
    # Each debt i can be paid at turns 0, 1, ..., T_i where T_i = floor((P - H_i) / G_i) if H_i <= P, else impossible.
    
    # This is a bipartite matching / scheduling problem:
    # Each debt has a deadline T_i (last turn it can be paid), and we need to schedule N debts
    # on N distinct turns. This is feasible iff when we sort by deadline, each debt i (0-indexed after sorting)
    # has deadline >= i.
    
    # This is the classic "scheduling with deadlines" greedy: sort by deadline ascending,
    # and check that the j-th job (0-indexed) has deadline >= j.
    
    deadlines = []
    for H, G in debts:
        if H > P:
            print("No")
            return
        # max turn (0-indexed) at which we can pay: floor((P - H) / G)
        T = (P - H) // G
        deadlines.append(T)
    
    deadlines.sort()
    
    for j in range(N):
        if deadlines[j] < j:
            print("No")
            return
    
    print("Yes")

solve()

---

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