Official

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\) を出力してしまい、不正解になります。

アルゴリズム

  1. \(N\) と \(A\) を読み取ります。
  2. 現在の細菌の数を表す x を \(A\) で初期化し、出力用のリスト out を用意します。
  3. 次の処理を \(N\) 回繰り返します。
    • x を文字列に変換して out に追加します。
    • x を \(2\) 倍し、翌日の細菌の数に更新します。
  4. 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: