概要

\(N\) 個の部屋それぞれでドアを1つ選ぶとき、経路の総数（組み合わせの数）を求める問題です。各部屋のドアの数をすべて掛け合わせれば答えになります。

考察

重要な気づき：積の法則

各部屋で選ぶドアは独立です。つまり、ある部屋でどのドアを選んでも、次の部屋で選べるドアの選択肢は変わりません。

このような場合、組み合わせの総数は積の法則（乗法原理）により求められます。

独立な \(N\) 個の選択があり、\(i\) 番目の選択肢が \(A_i\) 通りあるとき、全体の組み合わせは \(A_1 \times A_2 \times \cdots \times A_N\) 通りである。

具体例

例えば \(N = 3\) で、各部屋のドアの数が \(A_1 = 2, A_2 = 3, A_3 = 2\) の場合：

• 部屋1：ドア1 or ドア2（2通り）
• 部屋2：ドア1 or ドア2 or ドア3（3通り）
• 部屋3：ドア1 or ドア2（2通り）

経路の総数は \(2 \times 3 \times 2 = 12\) 通りです。

オーバーフローについて

\(A_i\) は最大 \(10^{18}\) と非常に大きいですが、制約に \(A_1 \times A_2 \times \cdots \times A_N \leq 10^{18}\) とあるため、最終的な答えは \(10^{18}\) 以下に収まります。Python は整数の桁数に上限がないため、オーバーフローの心配は不要です。

アルゴリズム

1. \(N\) を読み込む
2. 変数 result を \(1\) で初期化する
3. \(N\) 回繰り返し、各 \(A_i\) を読み込んで result に掛ける
4. result を出力する

これは単純に \(A_1 \times A_2 \times \cdots \times A_N\) を計算しているだけです。

N = int(input())
result = 1
for _ in range(N):
    result *= int(input())
print(result)

計算量

• 時間計算量: \(O(N)\) — 各部屋のドア数を1回ずつ読み込み、掛け算するだけ
• 空間計算量: \(O(1)\) — 累積の積を保持する変数1つのみ

実装のポイント

• Python の多倍長整数: C++ などでは \(10^{18}\) を超える掛け算の途中結果でオーバーフローする可能性がありますが、Python では整数に上限がないため特別な対策は不要です。

• 入力の読み込み: \(A_i\) を1つずつ読み込みながら掛け算することで、配列に保存する必要がなく、空間効率が良くなります。

  ソースコード

N = int(input())
result = 1
for _ in range(N):
    result *= int(input())
print(result)

---

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