概要

\(N\) 種類の植物がそれぞれ異なる初期高さと成長速度を持つとき、全ての植物が目標高さ \(M\) cm 以上になるまでの最小日数を求める問題です。

考察

重要な気づき

1. 各植物は独立に成長する: \(i\) 番目の植物の \(d\) 日目の高さは \(A_i + B_i \times d\) cm です。

2. 「全ての植物が \(M\) cm 以上」という条件: これは「最も成長が遅い植物が \(M\) cm に達する日」を求めることと同じです。言い換えると、各植物が \(M\) cm に達するのに必要な日数の最大値を求めればよいです。

3. 各植物に必要な日数の計算: \(i\) 番目の植物が \(M\) cm 以上になるには、

   • \(A_i \geq M\) なら、最初から条件を満たしているので \(0\) 日
   • \(A_i < M\) なら、\(A_i + B_i \times d \geq M\) を満たす最小の整数 \(d\) を求める

必要日数の導出

\(A_i + B_i \times d \geq M\) を変形すると： $\(d \geq \frac{M - A_i}{B_i}\)$

日数は整数なので、\(\frac{M - A_i}{B_i}\) を切り上げた値が必要な日数になります。

具体例

\(M = 10\) cm の場合を考えます： - 植物1: \(A_1 = 3\), \(B_1 = 2\) → 必要な成長量は \(7\) cm、日数 = \(\lceil 7/2 \rceil = 4\) 日 - 植物2: \(A_2 = 8\), \(B_2 = 1\) → 必要な成長量は \(2\) cm、日数 = \(\lceil 2/1 \rceil = 2\) 日 - 植物3: \(A_3 = 12\), \(B_3 = 3\) → 既に \(M\) 以上なので \(0\) 日

全植物が \(M\) cm 以上になるのは \(\max(4, 2, 0) = 4\) 日目です。

アルゴリズム

1. 各植物について、\(M\) cm 以上になるために必要な日数を計算する
   • \(A_i \geq M\) なら \(0\) 日
   • そうでなければ \(\lceil (M - A_i) / B_i \rceil\) 日
2. 全植物の必要日数の最大値を出力する

計算量

• 時間計算量: \(O(N)\)
  • 各植物について定数時間で必要日数を計算し、\(N\) 回繰り返す
• 空間計算量: \(O(1)\)
  • 最大値を保持する変数のみ使用（入力を逐次処理）

実装のポイント

1. 切り上げの計算: Pythonでは math.ceil((M - A) / B) で切り上げ除算ができます。整数のみで計算したい場合は (M - A + B - 1) // B という式も使えます。

2. 初期条件のチェック: \(A_i \geq M\) の場合を先に処理することで、不要な計算を避けられます。

3. オーバーフローに注意: \(M\) や \(A_i\), \(B_i\) は最大 \(10^9\) ですが、Pythonでは整数のオーバーフローが起きないため、そのまま計算できます。他の言語（C++など）では64ビット整数を使う必要があります。

   ソースコード

import math

def solve():
    N, M = map(int, input().split())
    
    max_days = 0
    for _ in range(N):
        A, B = map(int, input().split())
        if A >= M:
            # Already at or above target height
            days_needed = 0
        else:
            # Need (M - A) / B days, rounded up
            days_needed = math.ceil((M - A) / B)
        max_days = max(max_days, days_needed)
    
    print(max_days)

solve()

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