AtCoder の問題を解くために必要な実力を付けるために作られた「典型問題」を解いていく企画として、「典型90」があります。

今回は、その内、の52問目である「 Dice Product（★3）」を解説していきたいと思います。
なにか、間違っているところなどありましたら、@EitaSugiまで、ご指導ご鞭撻の程、よろしくお願い致します！

問題名　【052 – Dice Product（★3）】

問題

考察

サイコロの出目の総積を効率的に計算する方法

考察

考えた内容の概要

この問題は、N個のサイコロの出目の総積を求めるものです。直接全ての組み合わせを計算すると、6^N通りの組み合わせが考えられるため、計算量が非常に大きくなります。このため、効率的な計算方法が求められます。

考えたことの内容

サイコロの出目の総積を求める際、それぞれのサイコロの出目の和を先に計算し、その後その和の総積を計算することで、計算量を削減することができます。

具体例を交えた説明

例として、3個のサイコロがある場合を考えます。それぞれのサイコロの出目は以下のようになっているとします。

サイコロ1: 1, 2, 3, 4, 5, 6
サイコロ2: 2, 3, 4, 5, 6, 7
サイコロ3: 3, 4, 5, 6, 7, 8
この場合、それぞれのサイコロの出目の和は以下のように計算できます。

サイコロ1の出目の和: 1 + 2 + 3 + 4 + 5 + 6 = 21
サイコロ2の出目の和: 2 + 3 + 4 + 5 + 6 + 7 = 27
サイコロ3の出目の和: 3 + 4 + 5 + 6 + 7 + 8 = 33
この結果を用いて、3個のサイコロの出目の総積の和を計算すると、以下のようになります。

総積の和: 21 × 27 × 33 = 18,711
このように、それぞれのサイコロの出目の和を先に計算することで、総積の和を効率的に計算することができます。

実装した内容

具体的には、まずそれぞれのサイコロの出目の和を計算し、その和を用いて総積を計算します。この方法を用いることで、計算量を大幅に削減することができます。

コード

以下に、実装したPythonコードを示します。

N = int(input())
box = []
mod = 10**9+7
cnt = 1
for i in range(N):
    A = list(map(int, input().split()))
    A_sum = sum(A)
    cnt *= A_sum
    cnt %= mod
print(cnt)

このコードでは、まずそれぞれのサイコロの出目の和を計算しています。その後、その和を用いて総積を計算し、最終的な結果を出力しています。

まとめ

前の問題【051 – Typical Shop（★5）】
次の問題【056 – Lucky Bag（★5）】