概要

初期状態でサイズ \(1\) のコロニーが \(1\) つある状態から、「全コロニーが自身の \(2\) 倍のサイズのコロニーを生成する」という操作を \(K\) 回繰り返したとき、最終的に存在するコロニーのサイズが何種類あるかを求める問題です。

考察

この問題のポイントは、増殖のルールを整理して、ステップごとの「サイズの集合」の変化を観察することです。

1. 初期状態（増殖 0 回目）

   • 存在するコロニーのサイズ: \(\{1\}\)
   • サイズの種類数: \(1\) （\(2^0\) のみ）

2. 増殖 1 回目

   • 元からあるサイズ: \(\{1\}\)
   • 新しく生まれるサイズ: \(1 \times 2 = 2\)
   • 全体のサイズ: \(\{1, 2\}\)
   • サイズの種類数: \(2\) （\(2^0, 2^1\)）

3. 増殖 2 回目

   • 元からあるサイズ: \(\{1, 2\}\)
   • 新しく生まれるサイズ: \(1 \times 2 = 2, \ 2 \times 2 = 4\)
   • 全体のサイズ: \(\{1, 2, 2, 4\}\)
   • 種類（重複を除く）: \(\{1, 2, 4\}\)
   • サイズの種類数: \(3\) （\(2^0, 2^1, 2^2\)）

4. 増殖 3 回目

   • 元からあるサイズ: \(\{1, 2, 2, 4\}\)
   • 新しく生まれるサイズ: \(2, 4, 4, 8\)
   • 全体のサイズ: \(\{1, 2, 2, 4, 2, 4, 4, 8\}\)
   • 種類（重複を除く）: \(\{1, 2, 4, 8\}\)
   • サイズの種類数: \(4\) （\(2^0, 2^1, 2^2, 2^3\)）

重要な気づき

増殖を繰り返すと、新しいサイズとして常に「現在の最大のサイズ \(\times 2\)」が追加されていきます。 \(K\) 回目の増殖が終わったとき、存在するコロニーのサイズの種類は \(\{2^0, 2^1, 2^2, \dots, 2^K\}\) となります。 この集合に含まれる要素の個数は \(K + 1\) 個です。

なぜシミュレーションでは解けないか

制約を確認すると \(K \leq 10^{18}\) と非常に大きな値になっています。 実際にコロニーのリストを作ったり、増殖を 1 回ずつシミュレーションしたりすると、時間切れ（TLE）やメモリ不足になってしまいます。しかし、上記の考察から「答えは常に \(K + 1\) である」という法則が導き出せるため、計算なしで答えを出すことができます。

アルゴリズム

1. 入力 \(K\) を読み込む。
2. \(K + 1\) を計算して出力する。

計算量

• 時間計算量: \(O(1)\)
  • \(K\) の値に関わらず、一度の加算のみで答えが求まります。
• 空間計算量: \(O(1)\)
  • 特殊なデータ構造は必要ありません。

実装のポイント

• 大きな数の扱い: \(K\) は最大で \(10^{18}\) に達するため、プログラミング言語によっては 64 ビット整数型（Python であれば通常の int）を使用する必要があります。

• 入力の読み込み: \(K\) が非常に大きいため、文字列として読み込んでから数値に変換するのが一般的です。

  ソースコード

import sys

def solve():
    # 標準入力から K を読み込む
    # 制約: 1 <= K <= 10^18
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    k = int(input_data[0])
    
    # 実験の推移を考える：
    # 開始時: サイズ {1} のコロニーが存在する（種類数: 1）
    # 1回目の増殖: {1} からサイズ 2 のコロニーが生まれ、元の 1 も残る -> {1, 2} （種類数: 2）
    # 2回目の増殖: {1, 2} のそれぞれから 2倍のサイズ (2, 4) が生まれ、元も残る -> {1, 2, 2, 4} （種類数: 3）
    # 3回目の増殖: {1, 2, 2, 4} から (2, 4, 4, 8) が生まれ、元も残る -> {1, 2, 2, 4, 2, 4, 4, 8} （種類数: 4）
    # 
    # このように、K 回の増殖後には {2^0, 2^1, 2^2, ..., 2^K} という K+1 種類のサイズが存在することになる。
    # したがって、求める種類数は K + 1 である。
    
    print(k + 1)

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-preview によって生成されました。