ABC200 C - Ringo's Favorite Numbers 2 を解いた

まともに全探索するとO(N^2)となるので無理。

確か、倍数を問う問題は、
その倍数で割った余りの集合から共通項の組み合わせで求められる気がする。

書いてみた。

abc200c.py

N = int(input())
A = list(map(int,input().split()))
A_ = list(map(lambda x:x%200,A))

# print(A)
# print(A_)

from collections import Counter
KEYs = list(set(A_))
lis = Counter(A_)

score = 0
for key in KEYs:
    if lis[key] > 1:
        score += ( lis[key]*(lis[key]-1) )//2

print(score)

counter じゃなくても 辞書でも同じアプローチが出来る。