概要

各植物の初期の高さと成長速度が与えられるので、すべての植物が指定された高さ \(M\) 以上になる最短の日数を求めます。

考察

各植物 \(i\) は、日数 \(d\) に対して高さが \(A_i + B_i \times d\) で増えていきます。
すべての植物が \(M\) 以上になる日数 \(d\) を求めたいので、それぞれの植物について「初めて高さが \(M\) 以上になる日数」を求め、その中の最大値を取ればよいです。

具体的には、各植物について次の不等式を解きます： $\( A_i + B_i \times d \geq M \)\( 変形すると： \)\( B_i \times d \geq M - A_i \Rightarrow d \geq \frac{M - A_i}{B_i} \)\( この右辺を小数で求めた後、**最小の整数 \)d$** を得るために「切り上げ」を行う必要があります。これは math.ceil を使うことで実現できます。

ただし、すでに初期の高さ \(A_i\) が \(M\) 以上であれば、その植物は0日目から条件を満たしているので、日数は0日でOKです。

素朴なアプローチとして、日数を1ずつ増やしながら全植物が \(M\) 以上かどうかを毎回調べると、答えが非常に大きくなる可能性があるため、時間内に終わらず TLE（Time Limit Exceeded）になります。
そこで、各植物ごとに必要な日数を直接計算することで、効率的に答えを求めます。

アルゴリズム

1. 各植物について、\(A_i \geq M\) なら日数は0。
2. そうでない場合は、\(d \geq \frac{M - A_i}{B_i}\) の小数を計算し、それを 切り上げ て必要な日数を得る。
3. 全植物の必要日数の最大値を取ったものが答え。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\)（入力を除く）

実装のポイント

• 切り上げには math.ceil() を使用する。
• 整数同士の割り算を行うときは一度浮動小数点にしないと、正確な切り上げができない場合があるため注意（ただしPythonでは安全に動作する）。
• 初期の高さが既に条件を満たしている場合（\(A_i \geq M\)）は、日数0として扱う。

ソースコード

import math

def main():
    N, M = map(int, input().split())
    plants = [tuple(map(int, input().split())) for _ in range(N)]
    
    # 各植物がM以上になる日を計算し、その最大値を取る
    max_day = 0
    for A, B in plants:
        if A >= M:
            day = 0
        else:
            # A + B * d >= M を満たす最小のdを求める
            # B * d >= M - A
            # d >= (M - A) / B
            # 切り上げ
            day = math.ceil((M - A) / B)
        max_day = max(max_day, day)
    
    print(max_day)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。