AtCoder-ABC206 C - Swappable【Python解答例】

AtCoder Beginner Contest206のC問題についてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 206（Sponsored by Panasonic） - AtCoder

AtCoder Beginner Contest206 C - Swappable

C - Swappable

問題文

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

・1≤i

制約

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

解答例

import collections

n = int(input())

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

C = collections.Counter(A)

ans = 0
for i in range(n):
    ans += n - i - C[A[i]]
    C[A[i]] -= 1

print(ans)

解説

問題文の通り 1 <= i < j <= Nのとき、Ai≠Ajとなるi と ｊの組が何個なるか答える問題です。

Counterを使って出てくる整数の個数を数えました。

答えとなる値ansは、Aiにおいてn - i から 整数A[i]の出現回数C[A[i]]を引いた数を足し合わせた値です。
出現回数C[A[i]]は計算が終わった後に1 を引いていきます。

このループを抜けたらあとにansを出力すればOKでした。

ABC206の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com