概要

各植物が高さ \(M\) cm 以上になるまでに必要な日数をそれぞれ計算し、その最大値を答える問題です。

考察

各植物 \(i\) の \(d\) 日目の高さは \(A_i + B_i d\) です。
観察終了条件は「すべての植物で \(A_i + B_i d \ge M\)」なので、これは言い換えると

• 各植物ごとに「\(M\) に到達する最小日数 \(d_i\)」を求め、
• 全部そろうには \(d \ge d_i\) が全てで必要
• よって最小の \(d\) は \(\max_i d_i\)

になります。

素朴に \(d=0,1,2,\dots\) と日数を増やしながら全植物を毎回チェックすると、答えの \(d\) が大きい場合（最大で \(10^9\) オーダーになり得る）に到底間に合いません（TLE）。

そこで、各植物について必要日数を直接式で求めるのがポイントです。

植物 \(i\) が \(M\) に届く条件は - \(A_i \ge M\) なら最初から達成しているので \(d_i = 0\) - \(A_i < M\) なら \(A_i + B_i d \ge M\) より
\(d \ge \dfrac{M-A_i}{B_i}\)
ただし \(d\) は整数なので、最小の整数は切り上げが必要です。

切り上げは整数演算で [ d_i = \left\lceil \frac{M-A_i}{B_i} \right\rceil = \frac{(M-A_i) + (B_i-1)}{B_i} ] （整数除算）で求められます。

具体例：\(A=3, B=2, M=8\) のとき
\(M-A=5\)、\(\lceil 5/2\rceil=3\) 日必要（0日目3cm → 3日目9cm）。

アルゴリズム

1. 答え ans を \(0\) で初期化する。
2. 各植物 \((A_i, B_i)\) について：
   • もし \(A_i \ge M\) なら必要日数は \(0\) なので無視（ans は更新不要）。
   • もし \(A_i < M\) なら
     [ need = \left\lceil \frac{M-A_i}{B_i} \right\rceil = \frac{(M-A_i) + (B_i-1)}{B_i} ] を計算し、ans = max(ans, need) とする。
3. ans を出力する。

最終的に ans は \(\max_i d_i\) になり、全植物が \(M\) 以上になる最小の日数です。

計算量

• 時間計算量: \(O(N)\)（各植物を1回ずつ処理）
• 空間計算量: \(O(1)\)（入力を読みながら処理し、配列を持たない）

実装のポイント

• 切り上げ除算は need = (M - A + B - 1) // B を使う（ただし \(A < M\) のときのみ）。

• \(A \ge M\) の場合にその式を使うと負数が混ざって意図しない結果になり得るため、コードのように分岐するのが安全です。

• 制約が大きいので sys.stdin.readline を使って高速に入力します。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    ans = 0
    for _ in range(N):
        A, B = map(int, input().split())
        if A < M:
            need = (M - A + B - 1) // B
            if need > ans:
                ans = need
    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。