Official

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

gpt-6-astra-medium

概要

\(1\) 日目に \(A\) 匹いる細菌が、毎日 \(2\) 倍に増えます。この規則に従って、\(1\) 日目から \(N\) 日目までの細菌の数を順番に出力します。

考察

各日の細菌の数を書き出すと、次のようになります。

  • \(1\) 日目:\(A\)
  • \(2\) 日目:\(A \times 2\)
  • \(3\) 日目:\(A \times 2^2\)

\(i\) 日目までに細菌が \(2\) 倍になる回数は \(i-1\) 回なので、\(i\) 日目の細菌の数は

\(A \times 2^{i-1}\)

と求められます。

例えば \(N=4,\ A=3\) の場合、出力する数は順に \(3,\ 6,\ 12,\ 24\) です。

この問題では、各日の数をそのまま計算する素朴な方法で十分に間に合います。特別な高速化は必要ありません。ただし、\(1\) 日目はまだ増えていないため、指数を \(i\) にしてしまうと答えが \(2\) 倍になり、誤答になります。

アルゴリズム

  1. \(N\) と \(A\) を読み取ります。
  2. 変数 i を \(0\) から \(N-1\) まで順番に動かします。
  3. 各 i について、\(A \times 2^i\) を計算して出力します。

コード中の i は「\(1\) 日目から何日経過したか」を表しています。そのため、i = 0 のときに \(1\) 日目の数を、i = N-1 のときに \(N\) 日目の数を出力できます。

計算量

  • 時間計算量: \(O(N)\)(制約内の整数演算・べき乗計算を定数時間とみなします)
  • 空間計算量: \(O(1)\)(出力する値を配列などに保存しません)

実装のポイント

  • Python の ** はべき乗を表します。2 ** i で \(2^i\) を計算できます。^ はべき乗ではないので注意してください。

  • range(n) は \(0\) から \(N-1\) までの値を生成するため、ちょうど \(N\) 行出力できます。

  • 細菌の数は最大で \(10^9 \times 2^{29}\) となり、符号付き \(32\) ビット整数には収まりません。Python の整数は大きな値もそのまま扱えるため、このコードでは特別な対応は不要です。

    ソースコード

# 問題文から独立に実装
n, a = map(int, input().split())
for i in range(n):
    print(a * 2 ** i)


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

posted:
last update: