概要

バクテリアのコロニーが \(K\) 回増殖した後に存在するサイズの種類数を求める問題です。増殖のパターンを分析すると、答えは \(K + 1\) という単純な式で求められます。

考察

増殖のシミュレーション

まず、小さな \(K\) で実際にどのようなサイズのコロニーが存在するか確認してみましょう。

初期状態（\(K = 0\)） - サイズ：\(\{1\}\)（1種類）

1回目の増殖後（\(K = 1\)） - 元のコロニー（サイズ1）はそのまま残る - サイズ1のコロニーから、サイズ \(1 \times 2 = 2\) の新しいコロニーが生まれる - サイズ：\(\{1, 2\}\)（2種類）

2回目の増殖後（\(K = 2\)） - サイズ1から → サイズ2が生まれる - サイズ2から → サイズ4が生まれる - サイズ：\(\{1, 2, 4\}\)（3種類）

3回目の増殖後（\(K = 3\)） - サイズ1から → サイズ2が生まれる - サイズ2から → サイズ4が生まれる - サイズ4から → サイズ8が生まれる - サイズ：\(\{1, 2, 4, 8\}\)（4種類）

重要な気づき

この実験を観察すると、以下のことが分かります：

1. サイズは常に2の冪乗：\(1 = 2^0\), \(2 = 2^1\), \(4 = 2^2\), \(8 = 2^3\), …
2. \(K\) 回の増殖後に存在するサイズは \(2^0, 2^1, 2^2, \ldots, 2^K\) のみ
3. 種類数は \(K + 1\)

なぜこうなるかというと、サイズ \(2^i\) のコロニーは「初期のサイズ1のコロニーが \(i\) 回2倍になったもの」を意味します。\(K\) 回の増殖があれば、0回〜\(K\)回の2倍操作を受けたコロニーが存在し得るため、\(K + 1\) 種類となります。

素朴なアプローチの問題点

\(K\) が最大 \(10^{18}\) と非常に大きいため、実際にシミュレーションを行うことは不可能です。\(K\) 回ループを回すと、時間計算量が \(O(K)\) となり TLE になります。

解決策

上記の考察から、\(K\) 回の増殖後のコロニーの種類数は必ず \(K + 1\) になることが分かりました。したがって、ループを回さずに直接 \(K + 1\) を出力すればよいです。

アルゴリズム

1. 入力 \(K\) を受け取る
2. \(K + 1\) を出力する

計算量

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

実装のポイント

• \(K\) が最大 \(10^{18}\) と非常に大きいですが、Python では整数のオーバーフローを気にする必要がありません

• 問題の本質を見抜くことで、複雑なシミュレーションが不要になる典型的な数学的考察問題です

  ソースコード

K = int(input())
print(K + 1)

---

この解説は claude4.5opus によって生成されました。