概要

泳げる距離が \(C\) メートル以上になるまで、練習によって距離を \(B\) メートルずつ増やし、その回数を数えます。

考察

練習を \(1\) 回するごとに、泳げる距離は必ず \(B\) メートル伸びます。そのため、問題文の通りに練習を \(1\) 回ずつシミュレーションすれば答えを求められます。

この素朴な方法でも、今回の制約では十分に高速です。最も多くの練習が必要なのは \(A=1,\ B=1,\ C=10000\) の場合で、練習回数は \(9999\) 回です。したがって、繰り返し処理による TLE の心配はありません。

例えば \(A=3,\ B=2,\ C=8\) の場合、泳げる距離は次のように変化します。

• 練習前：\(3\) メートル
• \(1\) 回目の練習後：\(5\) メートル
• \(2\) 回目の練習後：\(7\) メートル
• \(3\) 回目の練習後：\(9\) メートル

初めて \(8\) メートル以上になるのは \(3\) 回目なので、答えは \(3\) です。

目標とちょうど同じ距離になる必要はありません。「\(C\) メートルになるまで」ではなく、「\(C\) メートル以上になるまで」繰り返すことが重要です。

アルゴリズム

1. 現在泳げる距離を a、練習によって伸びる距離を b、目標を c として読み込みます。
2. 練習回数を表す count を \(0\) にします。
3. a < c の間、次の処理を繰り返します。
   • a に b を加えます。
   • count を \(1\) 増やします。
4. count を出力します。

各繰り返しの後、a は count 回練習したときの泳げる距離を表します。目標未満の間だけ練習し、初めて目標以上になった時点で終了するので、必要な最小の練習回数が得られます。

計算量

必要な練習回数を \(K\) とします。\(A \geq C\) なら \(K=0\)、そうでなければ \(K=\left\lceil \frac{C-A}{B} \right\rceil\) です。

• 時間計算量: \(O(K+1)\)
  練習 \(1\) 回につき定数時間の処理を行います。
• 空間計算量: \(O(1)\)
  使用する変数の数は一定です。

実装のポイント

• 繰り返し条件は while a < c: とします。a <= c にすると、目標にちょうど到達した場合に余計な練習をしてしまいます。

• count を \(0\) から始めることで、最初から \(A \geq C\) の場合は繰り返しが一度も実行されず、そのまま \(0\) を出力できます。

• \(B \geq 1\) なので、練習するたびに泳げる距離は増え、繰り返しは必ず終了します。

  ソースコード

# 問題文から独立に実装: 目標に届くまで 1 回ずつ練習を繰り返す
a, b, c = map(int, input().split())
count = 0
while a < c:
    a += b
    count += 1
print(count)

---

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