概要

各部屋で選べるドアの数が与えられるので、入口から出口までの経路数は「各部屋の選び方の数の積」で求められます。
つまり、答えは \(A_1 \times A_2 \times \cdots \times A_N\) です。

考察

この問題では、各部屋でちょうど1つのドアを選びます。

• 部屋 \(1\) では \(A_1\) 通り
• 部屋 \(2\) では \(A_2\) 通り
• …
• 部屋 \(N\) では \(A_N\) 通り

というように、それぞれの部屋での選び方は独立です。
このとき、組合せの基本法則より、全体の通り数はそれらを掛け合わせればよいです。

たとえば、

• 部屋1にドアが2個
• 部屋2にドアが3個
• 部屋3にドアが4個

あるなら、経路数は

\(2 \times 3 \times 4 = 24\)

通りです。

なぜこれでよいのか

各部屋でどのドアを選んでも、必ず次の部屋に進めます。
つまり、「前の部屋でどのドアを選んだか」によって、次の部屋で選べるドアが変わることはありません。

そのため、単純に各部屋の選択肢数を掛け算すれば、すべての経路数を数えられます。

素朴な方法がなぜだめか

実際にすべての経路を列挙しようとすると、経路数は最大で \(10^{18}\) 通りになりえます。
これは到底試せる数ではないため、列挙は不可能です。

しかし、この問題は列挙する必要はなく、積を求めるだけでよいので、\(N\) 個の数を順に掛けるだけで解けます。

アルゴリズム

1. 変数 ans を \(1\) で初期化する
2. 各部屋について、入力された \(A_i\) を ans に掛ける
3. 最後に ans を出力する

計算量

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

実装のポイント

• 初期値を \(1\) にすることが重要です。掛け算の単位元なので、ここから順に \(A_i\) を掛けていけます。

• 制約で \(A_1 \times A_2 \times \cdots \times A_N \leq 10^{18}\) が保証されているため、答えは問題なく扱えます。

• 入力が最大 \(10^5\) 行あるので、コードのように sys.stdin.readline を使うと高速に読み込めます。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    ans = 1
    for _ in range(N):
        ans *= int(input())
    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.4-high によって生成されました。