Official

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

gpt-6-astra-medium

概要

その日の細菌の数を出力し、次の日に向けて \(2\) 倍にする操作を \(N\) 回繰り返します。

考察

細菌の数は毎日ちょうど \(2\) 倍になるので、前日の数が分かれば、その日の数も求められます。\(i\) 日目の細菌の数は \(A \times 2^{i-1}\) ですが、毎回べき乗を計算する必要はありません。

例えば \(N=4,\ A=3\) の場合、細菌の数は次のように変化します。

  • \(1\) 日目:\(3\) 匹
  • \(2\) 日目:\(6\) 匹
  • \(3\) 日目:\(12\) 匹
  • \(4\) 日目:\(24\) 匹

したがって、現在の数だけを変数に保存し、順番に出力すれば十分です。この素朴なシミュレーションで時間内に処理できます。

ただし、整数型の大きさには注意が必要です。出力する値は最大で \(10^9 \times 2^{29}\) となり、C++ の一般的な \(32\) ビット整数型 int には収まりません。オーバーフローによる誤答を防ぐため、細菌の数には long long を使います。

アルゴリズム

  1. 日数 \(N\) と初日の細菌の数 \(A\) を読み込みます。
  2. 現在の細菌の数を表す変数 cur を \(A\) で初期化します。
  3. 次の操作を \(N\) 回繰り返します。
    • cur を出力します。
    • cur = cur + cur として、次の日の細菌の数に更新します。

最初の出力時には cur は \(A\) です。その後、出力するたびに \(2\) 倍にするので、各日の細菌の数が順番に出力されます。

計算量

  • 時間計算量: \(O(N)\)
  • 空間計算量: \(O(1)\)

各日について出力と更新を一度ずつ行います。また、全日分の値を配列に保存する必要はありません。

実装のポイント

  • 出力してから \(2\) 倍にします。 先に \(2\) 倍にすると、初日の出力が \(2A\) になってしまいます。

  • ループをちょうど \(N\) 回実行し、各値の後に改行を出力します。

  • 入力値を保存する a と、現在の数を保存する cur には long long を使います。

  • 提示コードでは最終日の出力後にも更新します。その値は最大で \(10^9 \times 2^{30}\) ですが、これも long long の範囲に収まります。

    ソースコード

// 問題文から独立に実装: 前日の値を足して 2 倍にする
#include <iostream>
int main() {
    int n; long long a; std::cin >> n >> a;
    long long cur = a;
    for (int i = 0; i < n; ++i) { std::cout << cur << "\n"; cur = cur + cur; }
}


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

posted:
last update: