Official

A - 急増する細菌 / Rapidly Multiplying Bacteria Editorial by admin Editorial for printing

swe-2-high

解説

問題の整理

\(1\) 日目の細菌の数は \(A\) 匹で、毎日ちょうど \(2\) 倍になります。つまり \(i\) 日目の細菌の数は

\[A \cdot 2^{i-1}\]

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

アルゴリズム

変数 \(x\) を \(A\) で初期化し、\(N\) 回繰り返します。各反復で \(x\) を出力し、その後 \(x\) を \(2\) 倍に更新します。

  • \(i\) 回目の反復の直前には \(x = A \cdot 2^{i-1}\) が成り立つ(不変条件)。
  • 各反復で \(x\) を出力してから \(x \leftarrow 2x\) とするので、出力される値はちょうど \(A \cdot 2^{i-1}\) となる。

オーバーフローについて

最大値は \(i = N\) のときの \(A \cdot 2^{N-1}\) で、制約より \(A \le 10^9\)、\(N \le 30\) なので

\[A \cdot 2^{N-1} \le 10^9 \cdot 2^{29} = 536{,}870{,}912{,}000{,}000{,}000 \approx 5.4 \times 10^{17}\]

となり、64 ビット整数(C++ の long long など、約 \(9.2 \times 10^{18}\) まで表現可能)に十分収まります。Python では整数の大きさに制限がないためそのまま計算できます。

正当性の証明

主張: ループの \(i\) 回目(1-indexed)の反復で出力される値は \(A \cdot 2^{i-1}\) である。

証明(帰納法):

  • 基底: \(i = 1\) のとき、ループ開始前に \(x = A = A \cdot 2^0\) であり、そのまま出力されるので正しい。
  • 帰納段階: \(i\) 回目の出力が \(A \cdot 2^{i-1}\) であると仮定する。出力後に \(x\) は \(2\) 倍されるので、\(i+1\) 回目の反復の開始時に \(x = A \cdot 2^{i-1} \cdot 2 = A \cdot 2^i\) となり、これがそのまま出力される。よって \(i+1\) 回目も正しい。

以上より、すべての \(i = 1, \ldots, N\) について正しい値が順番に出力される。またループはちょうど \(N\) 回で終了し、出力は \(N\) 行となるので出力形式も満たす。

計算量

  • 時間計算量: \(O(N)\)
  • 空間計算量: \(O(1)\)(入力の整数 2 個と現在値 1 個のみ保持。Python 版は出力をリストに蓄積するため厳密には \(O(N)\) だが、C++ 版は各行を即時出力するので \(O(1)\) 補助空間)

posted:
last update: