概要

\(N\) 本の植物がそれぞれ異なる初期の高さ \(A_i\) と 1 日あたりの成長量 \(B_i\) を持っています。すべての植物の高さが \(M\) cm 以上になる最初の日（最小の非負整数 \(d\)）を求める問題です。

考察

「すべての植物が高さ \(M\) 以上になる日」を求めるには、まず「それぞれの植物が単体で高さ \(M\) 以上になるには何日かかるか」を考えます。

植物 \(i\) について、 \(d\) 日目の高さは \(A_i + B_i \times d\) です。これが \(M\) 以上になる条件は以下の通りです。 $\(A_i + B_i \times d \geq M\)$

この不等式を \(d\) について解くと： 1. すでに \(A_i \geq M\) の場合： \(d = 0\) 日で条件を満たします。 2. \(A_i < M\) の場合： $\(B_i \times d \geq M - A_i\)\( \)\(d \geq \frac{M - A_i}{B_i}\)$

\(d\) は整数である必要があるため、条件を満たす最小の整数 \(d_i\) は \(\frac{M - A_i}{B_i}\) を切り上げた値になります。

すべての植物が条件を満たすためには、各植物が必要とする日数 \(d_i\) のうち、最も大きい値（最大値）が答えとなります。

アルゴリズム

1. 答えとなる変数 max_d を \(0\) で初期化します。
2. 各植物 \(i = 1, 2, \ldots, N\) について以下を繰り返します。
   • もし \(A_i < M\) ならば：
     • \(d_i = \lceil \frac{M - A_i}{B_i} \rceil\) を計算します。
     • max_d と \(d_i\) を比較し、大きい方を新しい max_d とします。
3. 最終的な max_d を出力します。

計算量

• 時間計算量: \(O(N)\) 植物の数 \(N\) に対して 1 回ずつループを回して計算を行うため、線形時間で解くことができます。
• 空間計算量: \(O(N)\) 入力値をすべてリストに格納する場合 \(O(N)\) となります。1 つずつ読み込んで処理する場合は \(O(1)\) に抑えることも可能です。

実装のポイント

切り上げの計算

プログラミングにおける整数計算で、正の数 \(X, Y\) に対して \(X / Y\) の切り上げ（\(\lceil X/Y \rceil\)）を求めるには、以下のテクニックがよく使われます。

# (X + Y - 1) // Y
d = (M - A + B - 1) // B

これにより、浮動小数点数（float）を使わずに誤差のない整数演算のみで切り上げを計算できます。

高速な入力

Python で \(N = 2 \times 10^5\) 程度の入力を処理する場合、input() を繰り返すと実行時間が長くなることがあります。sys.stdin.read().split() を使って一括で読み込むことで、実行時間を大幅に短縮できます。

ソースコード

import sys

def solve():
    # 入力を一括で読み込み、スペースや改行で分割してリストにする
    # Nが2*10^5程度であれば、この方法がPythonでは高速です
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # イテレータを使用して順番に値を取得する
    it = iter(input_data)
    N = int(next(it))
    M = int(next(it))
    
    max_d = 0
    for _ in range(N):
        A = int(next(it))
        B = int(next(it))
        
        # すでに高さがM以上の場合は、必要な日数は0日
        # 高さ A + B * d >= M となる最小の非負整数 d を求める
        if A < M:
            # A + B * d >= M
            # B * d >= M - A
            # d >= (M - A) / B
            # 最小の整数 d は ceil((M - A) / B)
            # 整数演算では (x + y - 1) // y で切り上げを計算できる
            d = (M - A + B - 1) // B
            if d > max_d:
                max_d = d
    
    # すべての植物が条件を満たす最小の日数は、各植物が必要とする日数の最大値
    print(max_d)

if __name__ == '__main__':
    solve()

---

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