競プロ典型 90 問：055 - Select 5（★2）

問題

atcoder.jp

挑戦結果

• 挑戦日：2021/10/21
• 結果：解けなかった(TLE)
• 時間：30分

考えたこと

• コンビネーションで全列挙は簡単にかけるけど、 ぐらいになって、TLEしそう。
• でも高速な解法は思いつかないので、全列挙してみよう。TLEした。
• 解けなかった。

公式解説

https://twitter.com/e869120/status/1399859200046505984/photo/1

解説を読んだふりかえり

• まさかの全列挙で良かった。まぁ、★２だもんなぁ。
• = はOKらしい。
• 結局の所、自分の遅いところも解説に書いてあって、計算途中で巨大なintになると遅いということだった。
• %P を入れまくったら通った。あとコンビネーションよりも、ループで列挙したほうが早かった。

ソース

コンビネーションバージョン(2.7s)

from itertools import combinations
N,P,Q = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
combs = combinations(A,5)
ans = 0
for C in combs:
    if (C[0]*C[1]%P*C[2]%P*C[3]%P*C[4]%P)  == Q:
        ans += 1
print(ans)

ループバージョン(0.9s)

N,P,Q = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = 0

for a in range(N):
    for b in range(a+1, N):
        for c in range(b+1, N):
            for d in range(c+1, N):
                for e in range(d+1, N):
                    if A[a] * A[b]%P * A[c]%P * A[d]%P * A[e]%P == Q:
                        ans += 1
print(ans)