競プロ典型 90 問：https://atcoder.jp/contests/typical90/tasks/typical90_at

問題

atcoder.jp

挑戦結果

• 挑戦日：2021/10/17
• 結果：解けた
• 時間：10分

考えたこと

• 愚直に全パターンやると、 なのでTLE。
• 46の倍数だけを考えるので、mod 46だけを考えれば良さそう。
• たとえば、Aが[0,1,2,46, 92]とかだったら、0が3個、1が1個、2が1個のようにまとめてしまって良さそう。
• A,B,Cそれぞれで、mod 46での個数を数えたら、46の倍数になるものを全パターン求めてもでぜんぜんOK。

公式解説

https://twitter.com/e869120/status/1395873457259225091

解説を読んだふりかえり

• 自分の理解と同じっぽいのでOK。

ソース

N = int(input())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
C = [int(x) for x in input().split()]

AA = [0] * 46
BB = [0] * 46
CC = [0] * 46

for i in range(N):
    AA[A[i]%46] += 1
    BB[B[i]%46] += 1
    CC[C[i]%46] += 1

ans = 0
for i in range(46):
    for j in range(46):
        for k in range(46):
            if(i+j+k) % 46==0:
                ans += (AA[i] * BB[j] * CC[k])

print(ans)