Edit

【pythonでABC200を解説】C - Ringo's Favorite Numbers 2

問題概要

問題ページ

C - Ringo's Favorite Numbers 2
C - Ringo's Favorite Numbers 2

問題ページへ移動する

問題文

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

  • \(1 \le i < j \le N\)
  • \(A_i - A_j\) は \(200\) の倍数である。

制約

  • 入力は全て整数
  • \(2 \le N \le 2 \times 10^5\)
  • \(1 \le A_i \le 10^9\)

問題の考察

ACコード

import sys
import collections


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    a = list(map(int, input().rstrip('\n').split()))
    d = collections.defaultdict(int)
    for v in a:
        d[v % 200] += 1
    cnt = 0
    for k1, v1 in d.items():
        for k2, v2 in d.items():
            if (k1 - k2) % 200 == 0:
                if k1 == k2:
                    if v1 > 1:
                        cnt += v1 * (v1 - 1)
                else:
                    cnt += v1 * v2
    print(cnt // 2)


if __name__ == '__main__':
    solve()

-Edit