京セラプログラミングコンテスト2021 C - Ringo's Favorite Numbers 2【Python解答例】

f:id:ebisuke33:20210508234453p:plain

京セラプログラミングコンテスト2021(AtCoder Beginner Contest200)のC問題についてPythonの解答例を記事にしていきます。
KYOCERA Programming Contest 2021（AtCoder Beginner Contest 200） - AtCoder

AtCoder Beginner Contest200 C - Ringo's Favorite Numbers 2

C - Ringo's Favorite Numbers 2

問題文

200 という整数が大好きなりんごさんのために、次の問題を解いてください。
N 個の正整数からなる数列 A が与えられるので、以下の条件をすべて満たす整数の組 (i , j) の個数を求めてください。

・1 ≤ i < j ≤N
・Ai − Aj は 200 の倍数である。

制約

・入力は全て整数
・2 ≤ N ≤ 2×10^5
・1 ≤ Ai ≤ 10^9

解答例

n = int(input())

A = list(map(int, input().split()))

# Aiを200で割った余りの個数リスト
lis = [0 for _ in range(200)]

# Aiを200で割った余りの個数をリストにメモ
for i in range(n):
    tmp = A[i] % 200
    lis[tmp] += 1

# 求める場合の数を余りの個数ごとに計算
ans = 0
for j in range(200):
    num = lis[j] - 1
    if num > 0:
        ans += num * (num + 1) // 2

print(ans)