Problem:


Score : 400 points

Problem Statement

We have N balls. The i-th ball has an integer A_i written on it.

For each k=1, 2, ..., N, solve the following problem and print the answer.  

Find the number of ways to choose two distinct balls (disregarding order) from the N-1 balls other than the k-th ball so that the integers written on them are equal.

Constraints

3 \leq N \leq 2 \times 10^5

1 \leq A_i \leq N

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

For each k=1,2,...,N, print a line containing the answer.

Sample Input 1

5
1 1 2 1 2

Sample Output 1

2
2
3
2
3

Consider the case k=1 for example. The numbers written on the remaining balls are 1,2,1,2.

From these balls, there are two ways to choose two distinct balls so that the integers written on them are equal.

Thus, the answer for k=1 is 2.

Sample Input 2

4
1 2 3 4

Sample Output 2

0
0
0
0

No two balls have equal numbers written on them.

Sample Input 3

5
3 3 3 3 3

Sample Output 3

6
6
6
6
6

Any two balls have equal numbers written on them.

Sample Input 4

8
1 2 1 4 2 1 4 1

Sample Output 4

5
7
5
7
7
5
7
5



Sample input:
5
1 1 2 1 2


Sample output:
2
2
3
2
3

Submission status: Runtime Error

Solution code:
import math

N = int(input())
S = [int(_) for _ in input().split()]

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def solve(N, S):
    
    hoge = list(set(S))
    hoge_count = len(hoge)
    
    if hoge_count == N:
        for i in range(N):
            print(0)
        return 
    elif hoge_count == 1:
        for i in range(N):
            print(N+1)
        return 
    
    else:
        dist_counts = {}
        
        for i in hoge:
            # 個数を数える
            c = S.count(i)
            dist_counts[i] = [c, combinations_count(c, 2)]

        sums = 0
        for i in dist_counts.values():
            sums += i[1]

        for i in range(N):
            ind = dist_counts[S[i]]
            if ind[0]-1 >= 2:
                cal = sums - ind[1] + combinations_count(ind[0]-1, 2)
            else:
                cal = sums - ind[1]
            print(cal)
solve(N, S)

Submission status: Runtime Error

Solution code:
import math
N = int(input())
A = list(map(int, input().split()))

B=sorted(set(A))
sa = []
gokei = 0
for i in range(len(B)):
    x = A.count(B[i])
    if x == 1:
        continue
    elif x ==2:
        gokei += 1
        sa.append(1)
    else:
        y = x-1
        z = math.factorial(x)//(math.factorial(x-2)*math.factorial(2))
        gokei += z
        sa.append(z-math.factorial(y)//(math.factorial(y-2)*math.factorial(2)))

ans = [0]*(N+1)
for i in range(N):
    z = A[i]
    if ans[z] == 0:
        e = gokei - sa[B.index(z)]
        ans.append(e)
        print(e)
    else:
        print(ans[z])

Submission status: Runtime Error

Solution code:
from collections import Counter

n = int(input())
a_li = list(map(int, input().split()))

ans_sum = 0

counter = Counter(a_li)
print(counter)

for i in counter:
    ans_sum += i*(i - 1)//2

for a in a_li:
    count = counter[a]
    if count == 1:
        print(ans_sum)
    else:
        print(ans_sum - count*(count - 1) // 2 + (count - 1)*(count - 2) // 2)

Submission status: Runtime Error

Solution code:
import collections
from math import factorial
N = int(input())
A = list(map(int,input().split()))
ans = 0
aa = collections.Counter(A)
for i in range(N):
    for k,v in aa.items():
        if k == A[i]:
            if v >= 3:
                num = factorial(v-1) / factorial(2) / factorial(v - 3)
                ans += num
        else:
            if v >= 2:
                num = factorial(v) / factorial(2) / factorial(v - 2)
                ans += num
    print(int(ans))
    ans = 0

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
import collections

c = collections.Counter(a)
values, counts = zip(*c.most_common())
if counts[-1] == 1:
	k = counts.index(1)
	del counts[k:]


from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

from collections import deque
t = deque()
for i in counts:
    t.append(cmb(i,2))

t = list(t)
ans = sum(t)

for i in a:
	print(ans - c[i] + 1)

Submission status: Runtime Error

Solution code:
from collections import Counter
import sys
input = sys.stdin.readline

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**4
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )


l = int(input())
#A=list(map(int, input().split()))
A=[int(i) for i in input().split()]

S = Counter(A)

for i in range(l):
  tmp = []
  S[A[i]] -= 1
  for j in S.keys():
    tmp.append(cmb(S[j],2,mod))
  S[A[i]] += 1
  print(sum(tmp))

Submission status: Runtime Error

Solution code:
from collections import Counter
from math import factorial

N = int(input())
A = list(map(int, input().split()))
c = Counter(A)

for k in range(N):
  sum_k = 0
  temp_c = c.copy()
  temp_c[A[k]] -= 1
  for v in temp_c.values():
    if v > 1:
      sum_k += factorial(v) / 2 / factorial(v - 2)
  print(int(sum_k))

Submission status: Runtime Error

Solution code:
#D
from collections import Counter
from copy import deepcopy
n = int(input())
a = list(map(int, input().split()))
def x(i):
    if i < 0:
        return 0
    if i == 1:
        return 1
    else:
        return x(i - 1) + i

for j in range(n):
    b=deepcopy(a)
    b.pop(j)
    # print(a,b)
    b = Counter(b)
    ans = 0
    # print(b)
    for i in range(1, max(b) + 1):
        # print(b[i])
        ans += x(b[i]-1)
    print(ans)

Submission status: Runtime Error

Solution code:
from collections import Counter


from operator import mul
from functools import reduce


def cmb(n, r):
    if (n < r):
        return 0
    r = min(n-r, r)
    if r == 0:
        return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under


N = int(input())
A = list(map(int, input().split()))
c = Counter()
for i in A:
    c.update(str(i))
cmbL = {}
gsum = 0

for i in c.keys():
    tmp1 = cmb(int(c[i]), 2)
    tmp2 = tmp1 - (tmp1 * (1 - 2/c[i]))
    cmbL[i] = [tmp1, tmp2]
    gsum += tmp1

for i in A:
    print(int(gsum - cmbL[str(i)][1]))

Submission status: Runtime Error

Solution code:
import math
N = int(input())
A = list(map(int, input().split()))

B=sorted(set(A))
sa = []
gokei = 0
for i in range(len(B)):
    x = A.count(B[i])
    if x == 1:
        continue
    elif x ==2:
        gokei += 1
        sa.append(1)
    else:
        y = x-1
        z = math.factorial(x)//math.factorial(x-2)//math.factorial(2)
        gokei += z
        sa.append(z-math.factorial(y)//math.factorial(y-2)//math.factorial(2))

ans = [0]*(N+1)
for i in range(N):
    z = A[i]
    if ans[z] == 0:
        e = gokei - sa[B.index(z)]
        ans.append(e)
        print(e)
    else:
        print(ans[z])

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))

import math
def combinations_count(n, r):
    ret = 0
    if n >= r :
        ret = math.factorial(n) // (math.factorial(n - r) *2
    return ret

dupl = [x for x in set(A) if A.count(x) > 1]
for i in range(N):
    ans = 0
    l = A[:]
    l.pop(i) 
    for j in dupl:
        p = combinations_count(l.count(j),2) 
        if p > 0:
            ans = ans + p
    print(ans)

Submission status: Runtime Error

Solution code:
import copy
import collections
import math
import sys
import numpy as np

def combinations_count(n, r):
    if n <= 1:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

N = int(input())
A = [int(i) for i in input().split()] 

bigC = collections.Counter(A)
vals = np.array(list(bigC.values()))
if (vals >= 2).any() == False:
  for _ in range(N):
    print(0)
  sys.exit()

maxnum = max(A)
lis = [-1] * maxnum
for i, a in enumerate(A):
  if lis[a-1] < 0:
    newA = copy.deepcopy(A)
    newA.pop(i)
    c = collections.Counter(newA)
    total = 0
    for idx in c:
      total += combinations_count(c[idx], 2)
      
    lis[a-1] = total
    for x in bigC:
      if bigC[x] == bigC[a]:
        lis[x-1] = total
    print(total)
  else:
    print(lis[a-1])

Submission status: Runtime Error

Solution code:
import collections
n = int(input())
*a, = map(int, input().split())
counter = collections.Counter(a)
d = {}
for key, value in counter.items():
    d[key] = (value * (value - 1)) // 2

sum_d = {}
for k in range(n):
    if a[k] not in sum_d:
        if d[a[k]] > 0: tmp = ((counter[a[k]] - 1) * (counter[a[k]] - 2)) // 2
        sum_d[a[k]] = sum(d.values())  - d[a[k]] + tmp
        print(sum_d[a[k]])
    else:
        print(sum_d[a[k]])

Submission status: Runtime Error

Solution code:
n = int(input())
List=[int(l) for l in input().split()]
a = [0]*20010
for j in range(n):
    a[List[j]] += 1
c = 0
for i in range(20010):
    c = c+(a[i]*(a[i]-1))//2
for k in range(n):
    print(c-a[List[k]]+1)

Submission status: Runtime Error

Solution code:
import sys
import collections
from math import factorial
stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)

i_i = lambda: int(i_s())
i_l = lambda: list(map(int, stdin.readline().split()))
i_s = lambda: stdin.readline().rstrip()

N = i_i()
A = i_l()
h = {}
h[0] = 0
h[1] = 0
C = collections.Counter(A)

for v in C.values():
    if v >= 2:
        h[v] = factorial(v) / factorial(2) / factorial(v - 2)

for x in A:
    ans = 0
    tmp = C[x] - 1
    if tmp >= 2:
        if h.get(tmp):
             ans += h.get(tmp)
        else:
            h[tmp] = factorial(tmp) / factorial(2) / factorial(tmp - 2)
            ans += h[tmp]
    for c in C.keys():
        if x != c:
            v = C[c]
            if v >= 2:
                if h.get(v):
                    ans += h.get(v)
                else:
                    h[v] = factorial(v) / factorial(2) / factorial(v - 2)
                    ans += h[v]
    print(int(ans))

Submission status: Runtime Error

Solution code:
from collections import Counter


from operator import mul
from functools import reduce


def cmb(n, r):
    r = min(n-r, r)
    if r == 0:
        return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under


N = int(input())
A = list(map(int, input().split()))
c = Counter()
for i in A:
    c.update(str(i))
cmbL = {}
gsum = 0

for i in c.keys():
    tmp1 = cmb(int(c[i]), 2)
    tmp2 = tmp1 - (tmp1 * (1 - 2/c[i]))
    cmbL[i] = [tmp1, tmp2]
    gsum += tmp1

for i in A:
    print(int(gsum - cmbL[str(i)][1]))

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
IND = list(set(A))
CNT = [A.count(x) for x in IND]
# print(IND)
# print(CNT)
CONB = [x*(x-1)//2 for x in CNT]
# print(CONB)
SUM = sum(CONB)
CALC = [-1]*N
for i in A:
    if CALC[i] != -1:
        print(CALC[i])
    else:
        n = CNT[IND.index(i)]
        ans = SUM - CONB[IND.index(i)] + (n-1)*(n-2)//2
        CALC[i] = ans
        print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))

lib = [0] * n

def comb(n, r):
    if r == 0 or r == n:
        return 1
    elif r == 1:
        return n
    else:
        return (comb(n - 1, r - 1) + comb(n - 1, r))

for i in a:
    lib[i - 1] += 1

count = 0

for i in lib:
    if i >= 2:
        count += comb(i, 2)

for i in a:
    print(count - (lib[i - 1] - 1))

Submission status: Runtime Error

Solution code:
import collections
from math import factorial

n = int(input())
s = list(map(str, input().split()))
ss = ''.join(s)
#print(ss)
for i in range(n):
  sss = ss[:i] + ss[i+1:]
  c = collections.Counter(sss)
  #print(c)
  count=0
  for v in c.values():
    if v >= 2:
      vv = int(factorial(v) / factorial(2) / factorial(v-2))
      count += vv
  print(count)

Submission status: Runtime Error

Solution code:
from collections import Counter
import sys
input = sys.stdin.readline

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**4
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )


l = int(input())
#A=list(map(int, input().split()))
A=[int(i) for i in input().split()]

S = Counter(A)

for i in range(l):
  ans = 0
  S[A[i]] -= 1
  for j in S.keys():
    ans += cmb(S[j],2,mod)
  S[A[i]] += 1
  print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
numlist = [int(_) for _ in input().split()]
setnum = set(numlist)
nsum = 0

for i in setnum:
    dicnum[i] = numlist.count(i)
    if dicnum[i] >= 2:
        nsum += dicnum[i]*(dicnum[i]-1)//2
    else:
        del dicnum[i]

for j in range(n):
    ans = nsum
    if numlist[j] in dicnum:
        ans = ans - dicnum[numlist[j]] + 1
    print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
import collections
#重複のみ
a_rep = {x for x in set(a) if a.count(x)>1}

#全て
a_all = set(a)

#一度だけ
a_once = a_all - a_rep
c = collections.Counter(a)
values, counts = zip(*c.most_common())
if counts[-1] == 1:
	k = counts.index(1)
	del counts[k:]


from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

from collections import deque
t = deque()
for i in counts:
    t.append(cmb(i,2))

t = list(t)
ans = sum(t)

for i in a:
    if i in a_once:
        print(ans)
    else:
        print(ans - c[i] + 1)

Submission status: Runtime Error

Solution code:
from scipy.misc import comb

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

for k, val in enumerate(A):
    count = 0
    nums = [0] * N
    for i, v in enumerate(A):
        if k == i:
            continue
        nums[v] += 1
    combs = list(map(lambda n: int(comb(n, 2)), nums))
    print(sum(combs))

Submission status: Runtime Error

Solution code:
import sys
from math import factorial
# sys.stdin = open('input.txt')

nCr = {}
def cmb2(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]

def cmb(n, r):
    return int(factorial(n) / factorial(r) / factorial(n - r))

n = int(input())
a = [i for i in map(int, input().split())]

cnt = {}
for i in a:
    if i not in cnt.keys():
        cnt[i] = 1
    else:
        cnt[i] += 1

total = 0

for i in cnt.values():
    if i >= 2:
        total += cmb(i, 2)

for i in range(n):
    ans = total
    x = cnt[a[i]]
    if x >= 2:
        ans = total - cmb(x, 2)
    if x-1 >= 2:
        ans += cmb(x-1, 2)
    print(ans)

Submission status: Runtime Error

Solution code:
import collections
N = int(input())
a = input().split()

for j in range(N):
    sums = 0
    a1 = a.copy()
    a1.pop(j)
    ans = dict(collections.Counter(a1))
    for i in ans.values():
        if i < 2:
            continue
        else:
            sums += func(i)
    print(sums)
    #print(a1)
    #print(ans)

Submission status: Runtime Error

Solution code:
from math import factorial

def comb(n, r):
  if r > n:
    return 0
  else:
    return factorial(n) / factorial(r) / factorial(n - r)

def each_check(ls):
  nums = list(set(ls))
  total = 0
  for i in nums:
    count = ls.count(i)
    total += comb(count, 2)
  return int(total)

N = input()
L = list(map(int, input().split()))

for i in L:
  target = L.pop(0)
  print(each_check(L))
  L.append(target)

Submission status: Runtime Error

Solution code:
def inp():
    return input()
def iinp():
    return int(input())
def inps():
    return input().split()
def miinps():
    return map(int,input().split())
def linps():
    return list(input().split())
def lmiinps():
    return list(map(int,input().split()))
def lmiinpsf(n):
    return [list(map(int,input().split()))for _ in range(n)]

n = iinp()
q = lmiinps()

k = 1
l = 0
s = 0

a = sorted(q)
a.append(0)

b = [0]*(a[n-1])
d = [0]*(a[n-1])

def re(n):
  if n < 2:
    return 1
  return n*re(n-1)

def c(n):
  return re(n)//re(n-2)//2

for i in range(n):
    if a[i] == a[i+1]:
        k += 1
    else:
        l = c(k)
        s += l
        b[a[i]-1]=l
        d[a[i]-1]=k
        k = 1

for j in q:
    if d[j-1] == 0:
        continue
    p = s-((b[j-1])-((b[j-1] *(d[j-1]-2)) // d[j-1]))
    print(p)

Submission status: Runtime Error

Solution code:
import collections
import math


def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


N = int(input())
A = list(map(int, input().split()))
c = collections.Counter(A)
memo = {}
ans = 0
for k, v in c.items():
    if v > 1:
        memo[v] = combinations_count(v, 2)
        ans += memo[v]
total_ans = ans
for i in range(N):
    k_ball = A[i]
    if c[k_ball] > 2:
        if k_ball - 1 in set(memo.keys()):
            print(int(total_ans - (memo[c[k_ball]] - memo[c[k_ball - 1]])))
        else:
            print(
                int(
                    total_ans - (memo[c[k_ball]] - combinations_count(c[k_ball] - 1, 2))
                )
            )
    elif c[k_ball] > 1:
        print(total_ans - 1)
    else:
        print(total_ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int,input().split()))

from collections import Counter
from bisect import bisect_left

c = Counter(A)
keys, values = zip(*c.most_common())
ans = 0
for i in range(len(values)):
    ans += values[i]*(values[i]-1)//2


for i in range(N):
    l = bisect_left(keys,A[i])
    print(ans - values[l]*(values[l]-1)//2 + (values[l]-1)*(values[l]-2)//2)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int,input().split()))

b = a[:]
b.sort()

c = [[]for _ in range(n+1)]

ct = 1
tmp = b[1]
sum = 0
for j in range(1,n):
  if b[j] == b[j-1]:
    ct += 1
  else :  
    c[tmp].append(ct)
    cm = int(ct*(ct-1)/2)
    c[tmp].append(cm)
    cm1 = int((ct-1)*(ct-2)/2)
    c[tmp].append(cm1)
    sum += cm
    tmp = b[j]
    ct = 1

c[tmp].append(ct)
cm = int(ct*(ct-1)/2)
c[tmp].append(cm)
cm1 = int((ct-1)*(ct-2)/2)
c[tmp].append(cm1)
sum += cm      

for k in a:
  print(sum-c[k][1] + c[k][2])

Submission status: Runtime Error

Solution code:
from scipy.special import comb

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

for k, val in enumerate(A):
    count = 0
    nums = [0] * N
    for i, v in enumerate(A):
        if k == i:
            continue
        nums[v] += 1
    combs = list(map(lambda n: int(comb(n, 2)), nums))
    print(sum(combs))