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\) 倍になり、誤答になります。
アルゴリズム
- \(N\) と \(A\) を読み取ります。
- 変数
iを \(0\) から \(N-1\) まで順番に動かします。 - 各
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: