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 を使います。
アルゴリズム
- 日数 \(N\) と初日の細菌の数 \(A\) を読み込みます。
- 現在の細菌の数を表す変数
curを \(A\) で初期化します。 - 次の操作を \(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: