公式

A - 小雨の予報 / Light Rain Forecast 解説 by admin 印刷ページ

swe-2-high

解法

\(i\) 日目(\(1\)-indexed)の降水量は、初項 \(A\)・公差 \(B\) の等差数列の第 \(i\) 項なので

\[A + (i-1)B\]

です。したがって \(i = 1, 2, \ldots, N\) についてこの値を順に出力すればよいです。

実装では、変数 x を \(A\) で初期化し、各日の出力後に x に \(B\) を加算していきます。これにより式の評価を毎回行わなくても同じ列を生成できます。

なお、最大値は \(A + (N-1)B \le 10^9 + 99 \cdot 10^9 = 10^{11}\) となり 32 ビット整数に収まらないため、C++ では 64 ビット整数型(long long)を使います。Python の int は任意精度なのでそのまま計算できます。

正しさの証明

ループ不変条件:\(i\) 回目の反復の開始時点で x \(= A + (i-1)B\) が成り立つ(\(i = 1, \ldots, N\))。

  • 初期化:x \(= A\) であり、\(i = 1\) のとき \(A + 0 \cdot B = A\) なので成立。
  • 維持:\(i\) 回目の反復で x \(= A + (i-1)B\) を出力し、その後 x に \(B\) を加算するので、次の反復開始時には x \(= A + iB\) となる。
  • 終了:ループはちょうど \(N\) 回実行される。

よって \(i\) 行目に出力される値は \(A + (i-1)B\) であり、これは問題文の定義する \(i\) 日目の降水量(\(1\) 日目が \(A\)、以降前日比 \(+B\))と一致する。以上よりプログラムは正しい。

計算量

  • 時間計算量:\(O(N)\)(\(N\) 回の出力)
  • 空間計算量:\(O(1)\)(入力を配列として保持せず、変数 x のみを更新する)

タイブレークは存在しません(出力は一意に定まります)。

投稿日時:
最終更新: