解法

高橋君は最初 \(A\) メートル泳げる。練習を \(n\) 回行うと泳げる距離は \(A + Bn\) メートルになる。目標を達成するには \(A + Bn \geq C\) を満たす最小の非負整数 \(n\) を求めればよい。

• \(A \geq C\) の場合、すでに目標を達成しているので \(n = 0\)。
• \(A < C\) の場合、不等式を変形すると \(Bn \geq C - A\)、すなわち \(n \geq \dfrac{C - A}{B}\)。よって答えは \(\left\lceil \dfrac{C - A}{B} \right\rceil\)。

整数同士の切り上げ除算は \(\left\lceil \dfrac{x}{y} \right\rceil = \left\lfloor \dfrac{x + y - 1}{y} \right\rfloor\)（\(x \geq 0\), \(y > 0\)）で計算できるので、答えは \(\dfrac{(C - A) + B - 1}{B}\) の切り捨て除算で求まる。

正しさの証明

\(n\) 回練習した後の距離は \(A + Bn\) である（練習1回ごとに \(B\) 増えるので、帰納的に明らか）。

\(A \geq C\) の場合: \(n = 0\) で条件 \(A + B \cdot 0 = A \geq C\) を満たし、\(n\) は非負なので \(0\) が最小。出力は正しい。

\(A < C\) の場合: 出力する値を \(n^* = \lceil (C - A)/B \rceil\) とする。天井関数の定義より \(n^* \geq (C - A)/B\) なので \(A + Bn^* \geq C\) となり、\(n^*\) は条件を満たす。一方、任意の整数 \(n < n^*\) について \(n \leq n^* - 1 < (C-A)/B\) なので \(A + Bn < C\) となり条件を満たさない。よって \(n^*\) は条件を満たす最小の非負整数であり、出力は正しい。

計算量

• 時間計算量: \(O(1)\)
• 空間計算量: \(O(1)\)（入力は3つの整数のみで、追加の配列は使わない）