A - 急増する細菌 / Rapidly Multiplying Bacteria Editorial by admin Editorial for printing
gpt-6-astra-medium概要
細菌の数を \(A\) 匹から始め、毎日 \(2\) 倍にしながら、\(1\) 日目から \(N\) 日目までの個体数を順番に出力します。
考察
その日の細菌の数が分かれば、翌日の数はそれを \(2\) 倍するだけで求められます。したがって、現在の細菌の数を変数 x に保持し、日ごとに更新すれば十分です。
例えば、\(N=4,\ A=3\) の場合、細菌の数は次のようになります。
| 日数 | 細菌の数 |
|---|---|
| \(1\) 日目 | \(3\) |
| \(2\) 日目 | \(6\) |
| \(3\) 日目 | \(12\) |
| \(4\) 日目 | \(24\) |
この問題では、素直に \(N\) 日分をシミュレーションする方法で間に合います。細菌を \(1\) 匹ずつ管理する必要はなく、個体数だけを整数で管理することが重要です。
また、\(1\) 日目の数は \(A\) なので、その日の数を記録してから \(2\) 倍する順序にします。先に \(2\) 倍すると、最初に \(2A\) を出力してしまい、不正解になります。
アルゴリズム
- \(N\) と \(A\) を読み取ります。
- 現在の細菌の数を表す
xを \(A\) で初期化し、出力用のリストoutを用意します。 - 次の処理を \(N\) 回繰り返します。
xを文字列に変換してoutに追加します。xを \(2\) 倍し、翌日の細菌の数に更新します。
outの要素を改行で結合して出力します。
\(i\) 回目の繰り返しの開始時点で、x は \(A \times 2^{i-1}\) です。これは \(i\) 日目の細菌の数なので、この処理で各日の個体数を正しい順番で出力できます。
計算量
- 時間計算量: \(O(N)\)
- 空間計算量: \(O(N)\)
制約内の整数の演算や文字列変換を定数時間として扱っています。出力用のリストに \(N\) 日分の結果を保存するため、空間計算量は \(O(N)\) です。
実装のポイント
range(N)を使うことで、ちょうど \(N\) 日分の結果を記録します。out.append(str(x))をx *= 2より先に実行することが重要です。\(N\) 日目の細菌の数は \(A \times 2^{N-1}\) であり、32ビット整数の範囲を超える場合があります。Python の
intは大きな整数を扱えるため、そのまま計算できます。"\n".join(out)で各日の結果を改行区切りにし、末尾にも改行を付けて出力しています。ソースコード
def main():
import sys
N, A = map(int, sys.stdin.readline().split())
x = A
out = []
for _ in range(N):
out.append(str(x))
x *= 2
sys.stdout.write("\n".join(out) + "\n")
main()
この解説は gpt-6-astra-medium によって生成されました。
posted:
last update: