Edit

【pythonでABC206を解説】C - Swappable

問題概要

問題ページ

C - Swappable
C - Swappable

問題ページへ移動する

問題文

\(N\) 個の整数からなる配列 \(A=(A_1,A_2,...,A_N)\) が与えられるので、次の条件を全て満たす整数組 \((i,j)\) の数を求めてください。

  • \(1 \le i < j \le N\)
  • \(A_i \neq A_j\)

制約

  • 入力は全て整数
  • \(2 \le N \le 3 \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)
    d[a[0]] += 1
    total = 0
    for i in range(1, n):
        total += (i - d[a[i]])
        d[a[i]] += 1
    print(total)


if __name__ == '__main__':
    solve()

-Edit