概要

現在泳げる距離 \(A\) から、1 回につき \(B\) メートルずつ伸ばして、\(C\) メートル以上にするための最小の練習回数を求めます。足りない距離を \(B\) で割り、端数を切り上げることで計算できます。

考察

\(n\) 回練習した後に泳げる距離は \(A + nB\) メートルです。したがって、求めるのは \(A + nB \geq C\) を満たす最小の非負整数 \(n\) です。

まず、\(A \geq C\) なら、すでに目標を達成しているので答えは \(0\) です。

\(A < C\) の場合、足りない距離を \(\mathrm{need} = C - A\) とすると、必要な練習回数は \(\mathrm{need}\) を \(B\) で割って切り上げた値になります。

例えば、\(A = 10,\ B = 3,\ C = 18\) の場合、足りない距離は \(8\) メートルです。 - \(2\) 回練習すると \(16\) メートル泳げますが、目標には届きません。 - \(3\) 回練習すると \(19\) メートル泳げるので、答えは \(3\) です。

単に整数の割り算で \(8 / 3\) を計算すると、端数が切り捨てられて \(2\) となり、誤答になります。そこで、正の整数の切り上げ除算の公式を使います。

\(\left\lceil \dfrac{\mathrm{need}}{B} \right\rceil = \left\lfloor \dfrac{\mathrm{need} + B - 1}{B} \right\rfloor\)

なお、泳げる距離に \(B\) を足す操作を目標に届くまで繰り返す方法でも、この制約では十分間に合います。ただし、上の公式を使えば繰り返しなしで答えを求められます。

アルゴリズム

1. \(A, B, C\) を入力します。
2. \(A \geq C\) なら、\(0\) を出力して終了します。
3. 足りない距離 \(\mathrm{need} = C - A\) を求めます。
4. 整数の割り算で \((\mathrm{need} + B - 1) / B\) を計算し、出力します。

この回数は、足りない距離を埋めるために必要な回数を切り上げたものなので、目標を達成できる最小の練習回数です。

計算量

• 時間計算量: \(O(1)\)
• 空間計算量: \(O(1)\)

実装のポイント

• 最初に \(A \geq C\) を判定し、練習が不要な場合を処理します。

• 提示されたコードは C++ です。整数同士の / は、今回のように値が正の場合、小数部分を切り捨てます。そのため、割る前に \(B - 1\) を加えて切り上げを実現しています。

• 浮動小数点数を使わず、整数演算だけで正確に答えを求められます。

  ソースコード

// 問題文から独立に実装: 足りない距離を B で切り上げ割り算
#include <iostream>
int main() {
    long long a, b, c; std::cin >> a >> b >> c;
    if (a >= c) { std::cout << 0 << std::endl; return 0; }
    long long need = c - a;
    std::cout << (need + b - 1) / b << std::endl;
}

---

この解説は gpt-6-astra-medium によって生成されました。