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: Time Limit Exceeded

Solution code:
from math import factorial

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

def comb(n):
    return 0 if n < 2 else (factorial(n) // factorial(n - 2)) // 2

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

dosu = [0 for _i in range(n)]

for e in nums:
    dosu[e - 1] += 1

ans = [-1 for _i in range(n)]
combs = [comb(e) for e in dosu]
total = sum(combs)

for e in nums:
    if ans[e - 1] < 0:
        ans[e - 1] = total - combs[e - 1] + comb(dosu[e - 1] - 1)

    print(ans[e - 1])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
n = int(input())
items = tuple(map(int, sys.stdin.readline().rstrip().split()))


com = [-1] * 2000001
sumc = 0
que = deque([])
seen = []
for i in items:
    if com[i] != -1:
        nn = com[i]
    else:
        nn = items.count(i)
        com[i] = nn
    que.append(nn)
    if i in seen:
        continue
    seen.append(i)
    sumc += nn*(nn-1)//2

while que:
    q = que.popleft()
    if q <2:
        print(sumc-q*(q-1)//2)
    else:
        print(sumc-q+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

from math import factorial
from itertools import combinations
from collections import Counter
from copy import deepcopy
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



def main():
    n = int(input())
    a = list(map(int, input().split()))
    for i in range(n):
        #tmp_a = deepcopy(a)
        #tmp_a[i] = -1
        tmp = a[i]
        a[i] = -1
        tmp_a_c = Counter(a)
        tmp_a_cc = [tmp_a_c[i] for i in tmp_a_c if tmp_a_c[i] > 1]
        r = 0
        for cc in tmp_a_cc:
            r += cmb(cc, 2)
        print(r)
        a[i] = tmp


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env pypy3

import sys
sys.setrecursionlimit(10 ** 6)
memo = [1, 1]
def fact(n):
	if len(memo) > n:
		return memo[n]
	else:
		for i in range(len(memo), n+1):
			memo.append(memo[i-1] * i)
		return memo[n]
def main():
	n = int(sys.stdin.readline())
	a = list(map(int, sys.stdin.readline().split()))
	cnt = {}
	sumcase = 0
	for i in range(n):
		cnt[a[i]] = 0
	for i in range(n):
		cnt[a[i]] += 1
	# print(a, cnt)
	for ai in cnt:
		if cnt[ai] >= 2:
			sumcase += fact(cnt[ai]) // fact(2) // fact(cnt[ai]-2)
	for i in range(n):
		if cnt[a[i]] == 2:
			print(sumcase - fact(cnt[a[i]]) // fact(2) // fact(cnt[a[i]]-2))
		elif cnt[a[i]] > 2:
			#print("hoge", a,  cnt[a[i]], sumcase, cnt)
			print(sumcase - fact(cnt[a[i]]) // fact(2) // fact(cnt[a[i]]-2) + fact(cnt[a[i]]-1) // fact(2) // fact(cnt[a[i]]-3))
		else:
			print(sumcase)
main()

Submission status: Time Limit Exceeded

Solution code:
from scipy.misc import comb

N = int(input())
num_list = list(map(int, input().split()))
num_set = set(num_list)

# 全数あるときの組み合わせ
ans_dict_1 = {}
# 1個抜いたときの組み合わせ
ans_dict_2 = {}

for i in num_set:
  ans_dict_1[i] = comb(num_list.count(i),2,exact=True)
  ans_dict_2[i] = comb(num_list.count(i)-1,2,exact=True)

total = sum(ans_dict_1.values())

for i in num_list:
  print(total - ans_dict_1[i] + ans_dict_2[i])

Submission status: Time Limit Exceeded

Solution code:
import itertools
import collections

N = int(input())
AList = input().split(" ")
tempList = collections.Counter(AList)

for k in range(N):
    count = 0

    for key, value in tempList.items():
        if k <= len(AList) and key == AList[k]:
            value -= 1

        count += len(list(itertools.combinations(range(value), 2)))
    
    print(count)

Submission status: Time Limit Exceeded

Solution code:
# coding:utf-8
from math import factorial
from fractions import Fraction

# 組合せの総数
def comb(n, k):
    
    if n < 0 or k < 0:
        pdt = 0
    
    else:
        pdt = 1
        for s in range(1, k + 1):
            pdt *= Fraction(n - s + 1, s)
    
    # 戻り値をint型にするために分子を取り出す
    return pdt.numerator

def main():
    n = int(input())
    a = list(map(int, input().split()))
    count = 0

    a_uniq = list(set(a))
    for v in a_uniq:
        if int(a.count(v)) > 1:
            temp = comb(a.count(v), 2)
        else: temp = 0
        count = count + temp

    for i in range(n):
        print(count - a.count(a[i])+1)
    
if __name__ == '__main__' :
    main()

Submission status: Time Limit Exceeded

Solution code:
number=[]
result=[]
N=int(input())
A=list(map(int,input().split()))
for i in range(N+1):
  number.append(0)
  result.append(0)
i=0
for i in A:
    if i in range(N+1):
      number[i]+=1
    else:
      number[i]=1
i=0
for i in range(N):
  cnt=0
  kie=A.pop(i)
  number[kie]-=1
  if result[kie]==0:
    for j in range(N-1):
      if number[j]>=1:
        cnt+=int((number[j]*(number[j]-1))/2)
    result[kie]=cnt
  A.insert(i,kie)
  number[kie]+=1
i=0
for i in range(N):
  print(result[A[i]])

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from operator import mul
from functools import reduce


def combinations_count(n, r):
    if n > 1:
        r = min(r, n - r)
        numer = reduce(mul, range(n, n - r, -1), 1)
        denom = reduce(mul, range(1, r + 1), 1)
        return numer // denom
    else:
        return 0


n = int(input())
a = list(map(int, input().split()))
d = Counter(a)
c = [0 for _ in range(max(a))]
for k, v in d.items():
    c[k - 1] = combinations_count(v, 2)

for i in range(n):
    ans = sum(c)
    p = a[i]
    res = c[p - 1] * (d[p] - 2) / d[p]
    ans -= c[p - 1] - res
    print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
import collections
import copy
N=int(input())
list=[]
s=input().split()
for i in range(N):
    list.append(int(s[i]))

for y in range(N):
    list1=copy.copy(list)
    list1.pop(y)
    c = collections.Counter(list1)
    a=0
    for h in c.values():
        if h!=1:
            a+=(h*(h-1)/2)
    print(int(a))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=[int(x) for x in input().split()]
A_s=set(A)
Com=0
for k in A_s:
    x=A.count(k)
    Com+=int(x*(x-1)/2)
    
for i in range(N):
    y=A.count(A[i])
    print(Com-y+1)

Submission status: Time Limit Exceeded

Solution code:
# D - Banned K
N = int(input())
A = list(map(int, input().split()))

import copy as c
C = []
for i in range(N):
    C.append(A.count(i+1))

for k in range(N):
    C_tmp = c.copy(C)
    if C_tmp[A[k]-1] > 0:
        sum=0
        C_tmp[A[k]-1] = C_tmp[A[k]-1]-1
        C_tmp2 = [s for s in C_tmp if s > 1]
        for j in C_tmp2:
            sum = sum + j*(j-1)/2
        #print(C_tmp,C_tmp2,int(sum))
        print(int(sum))
    else:
        sum=0
        C_tmp2 = [s for s in C if s > 1]
        print(C),print(C_tmp2)
        for j in C_tmp2:
            sum = sum + j*(j-1)/2
        #print(C,C_tmp2,int(sum))
        print(int(sum))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
aList = list(map(int, input().split()))
acount = [aList.count(i)-1 for i in aList]
sums = sum(acount)
for i in acount:
    print((sums)//2 - i)

Submission status: Time Limit Exceeded

Solution code:

import collections
from math import factorial

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

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

for i in range(1, N + 1, 1):
    Except_Ak = A[:i-1] + A[i:]
    # print(Except_Ak)
    c = collections.Counter(Except_Ak)
    values, counts = zip(*c.most_common())
    counts_list = list(counts)
    elem_num_list = [e for e in counts_list if e > 1]
    # print(elem_num_list)
    count = 0

    for i in range(1, len(elem_num_list) + 1, 1):
        count = count + combinations_count(elem_num_list[i-1], 2)

    print(count)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
i=input('')
i=i.split(' ')
for a in range(n):
    i[a]=int(i[a])

found={str(i[0]):0}

for a in range(n):
    if str(i[a]) in found:
        found[str(i[a])]+=1
    else:
        found[str(i[a])]=1


num=[]
kai=[]
for a in found:
    num.append(int(a))
    kai.append(found[a])

for a in range(n):
    zen=0
    for b in range(len(num)):
        if i[a]==num[b]:
            cai=kai[b]-1
        else:
            cai=kai[b]
        
        if cai>=2:
            s=0
            for c in range(cai-1):
                s=s+(cai)
            s=s+1
            s=int(s/2)
            zen=zen+s
        else:
            zen=zen+0
    print(zen)

Submission status: Time Limit Exceeded

Solution code:
import sys


import sys
input = sys.stdin.readline

N = int(input())
A=list(map(int, input().split()))
ans = 0
for i in range(N):
    S = A[:]
    del(S[i])
    for j in range(N -1):
        for k in range(j+1,N -1):
            if(S[j] == S[k]):
                ans += 1
            else:
                pass
    print(ans)
    ans = 0

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

nums = list(map(int, input().split()))
temp = nums.copy()
for i in range(n):
    nums.pop(i)
    result = 0
    for v in set(nums):
        c = nums.count(v)
        if (c > 1):
            result += int(c*(c-1)/2)
    print(result)
    nums = temp.copy()

Submission status: Time Limit Exceeded

Solution code:

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

#print(A)
#x = A.count(1) #リストの中の値がｘである個数を返す
base = 0
for i in range(1,max(A)+1):
    x = A.count(i)
    if x > 1:
        base += int(x*(x-1)/2)

#print(base)
#print(A)
#print(A.count(A[3]))

for i in range(N):
    m = A.count(A[i])
    #print(m)
    if m == 1:
        ans = base
        print(ans)
    elif m == 2:
        ans = base -1
        print(ans)
    else:
        ans = int(base-m*(m-1)/2+(m-1)*(m-2)/2)
        print(ans)

Submission status: Time Limit Exceeded

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


for i in range(n):
  b = a[:]
  b.pop(i)
  r = 0
  for j in range(n):
    c = b.count(j)
    if c > 1:
      r += c * (c-1) / 2
    else:
      pass
  print(int(r))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from operator import mul
from functools import reduce

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


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

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 += cmb(v,2)
  print(int(sum_k))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N = int(input())
l = deque(list(input().split()))
ans = 0
for k in range(N):
  a = l.popleft()
  for x in set(l):
    ans += l.count(x)*(l.count(x)-1)/2
  print(int(ans))
  ans = 0
  l.append(a)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(x) for x in input().split()]
k = []
q = []
for i in a:
    if i not in k:
        k.append(i)
for i in k:
    q.append(a.count(i))
M = 0
for i in q:
    M += i*(i-1)//2
for i in range(n):
    w = a[i]
    if w in k:
        m = q[k.index(w)]
        print(M-m+1)
    else:
        print(M)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
from math import factorial

input = sys.stdin.readline

def conbi(n, r = 2):
    if n - r < 0:
        return 0
    return int(factorial(n) / (factorial(n - r) * factorial(r)))

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

for _ in A:
    ans = 0
    for cnt in A_cnt.keys():
        if A_cnt[cnt] == 1:
            continue
        else:
            if cnt == _:
                n = A_cnt[cnt] - 1
                ans += conbi(n)
            else:
                ans += conbi(A_cnt[cnt])
    print(ans)

Submission status: Time Limit Exceeded

Solution code:

import collections

n = int(input())
a = list(map(int, input().split()))
c_lst = []
c = collections.Counter(a)
for i in c.most_common()[::-1]:
    if i[1] >= 2:
        c_lst.append(list(i))
if c_lst:
    values, counts = zip(*c_lst)
else:
    values = []

cnt = []
for i in range(len(c_lst)):
    cnt.append((c_lst[i][1] * (c_lst[i][1] - 1)) // 2)
cnt_ = sum(cnt)
    
for i in a:
    ans = 0
    if i in values:
        ans += ((c_lst[values.index(i)][1] - 1) * (c_lst[values.index(i)][1] - 2)) // 2
        ans += cnt_ - cnt[values.index(i)]
    else:
        ans = cnt_
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
cnt_dict = {}
total = 0
for x in set(A):
  cnt = A.count(x)
  cnt_dict[x] = cnt
  if cnt > 1:
    total += int(cnt * (cnt - 1) / 2)
for i in range(N):
  ans = total - (cnt_dict[A[i]] - 1)
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
input()
aa = list(map(int, input().split()))
uu = list(set(aa))
cc = uu.copy()
total = 0
for i in range(len(uu)):
    cc[i] = aa.count(uu[i])
    total += cc[i] * (cc[i]-1) / 2

dic = dict(zip(uu,cc))

for a in aa:
    print(int(total - dic[a] + 1))

Submission status: Time Limit Exceeded

Solution code:
# from collections import deque
from collections import Counter
from scipy.misc import comb
# from scipy.special import comb

n = int(input())
k = list(map(int, input().split()))
for i in range(len(k)):
    ans = 0
    k_n = k.copy()
    k_n.pop(i)
    c = Counter(k_n)
    for key in c:
        ans += comb(c[key], 2, exact=True)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
N = int(input())
l = list(input().split())


for i in range(N):
    a_k = []
    a = 0
    a_k = copy.copy(l)
    a_k.pop(i)

    dic = {}

    for ll in a_k:
        dic[ll] = 0

    for ll in a_k:
        dic[ll] += 1

    for ll in dic.values():
        if int(ll)>1:
            a += ll*(ll-1)/2
    print(str(int(a)))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split(" ")))
import copy
import itertools
for v in range(n):
    a_ = copy.copy(a)
    del a_[v]
    count = 0
    x = list(itertools.combinations(a_, 2))
    for s in range(len(x)):
        if x[s][0] == x[s][1]:
            count+=1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy
from operator import mul
from functools import reduce


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


def main():
    n = int(input())
    As = list(map(int, input().split()))

    a_set = set(As)
    a_dict = {}
    for a in a_set:
        Bs = deepcopy(As)
        Bs.remove(a)
        b_set = set(Bs)
        a_dict[a] = 0
        for b in b_set:
            a_dict[a] += cmb(Bs.count(b), 2)

    for a in As:
        ans = a_dict[a]
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import collections

N = int(input())
num_list = list(input().split())
memo = [0]*(N+1)
memo_flg = [False]*(N+1)
c = collections.Counter(num_list)

def calc(k):
    target = num_list[k]
    num = int(target)
    if(memo_flg[num] is True):
        return memo[num]
    ans = 0
    
    test = dict(c)
    test[target] -= 1

    for i in test.keys():
        ans += (test[i]*(test[i]-1))//2
    memo[num] = ans
    memo_flg[num] = True
    return ans

[print(calc(i)) for i in range(N)]

Submission status: Time Limit Exceeded

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

aval = []
acount = []

for i in range(n):
    try:
        ind = aval.index(i)
    except:
        a = ao[0:i] + ao[i+1:n]
        count = 0
        target = [j for j in list(set(ao)) if ao.count(j) != 1]
        for t in target:
            tmp = a.count(t)
            count += sum([i for i in range(tmp-1, 0, -1)])
        print(count)
        aval.append(i)
        acount.append(count)
    else:
        print(acount[ind])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
n = int(input())
items = list(map(int, sys.stdin.readline().rstrip().split()))


com = [-1] * 2000001
sumc = 0
que = deque([])
seen = []
for i in items:
    if com[i] != -1:
        nn = com[i]
    else:
        nn = items.count(i)
        com[i] = nn
    que.append(nn)
    if i in seen:
        continue
    seen.append(i)
    sumc += nn*(nn-1)//2

while que:
    q = que.popleft()
    if q <2:
        print(sumc-q*(q-1)//2)
    else:
        print(sumc-q+1)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N = int(input())
A = input().split()
c = Counter(A)
a = list(c.values())
b = len(a)
AA = A
for i in range(N):
    r = 0
    x = AA.pop(i)
    c = Counter(AA)
    a = list(c.values())
    b = len(a)
    for j in range(b):
        r += (a[j]*(a[j]-1))/2
    AA.insert(i,x)
    print(int(r))

Submission status: Time Limit Exceeded

Solution code:
import collections

N = int(input())
listA = list(map(int, input().split()))
# 各数字の出現回数をカウント
countA = dict(collections.Counter(listA).most_common())
countA_calc = {}
countA_calc2 = {}
for i in listA:
    count = 0
    for x, y in countA.items():
        if x == i:
            if x not in countA_calc2:
                countA_calc2[x] = (y -1) * (y - 2) // 2
            count += countA_calc2[x]
        else:
            if x not in countA_calc:
                countA_calc[x] = y * (y -1) // 2 
            count += countA_calc[x]
    print(count)

Submission status: Time Limit Exceeded

Solution code:
import math
N = (int(input()))
items = list(map(int,input().split()))
for i in range(len(items)):    
    rest = items[:i] + items[i+1:]
    rest_unique = list(set(rest))
    out = 0
    for j in rest_unique:
        cnt = sum([1 for x in rest if x == j])
        if cnt >= 2:
            out = out + math.factorial(cnt)/math.factorial(cnt-2)/2
    print(int(out))

Submission status: Time Limit Exceeded

Solution code:
def cmb(n):
	if n<=1:
		return 0
	else:
		return int(n*(n-1)*0.5)
N = int(input())
A = [int(x) for x in input().split()]
ans=[0]*N
lists=[]
k=0
for i in range(N):
  l=cmb(A.count(A[i]))
  if not A[i] in lists:
	  k+=l
	  lists.append(A[i])
  ans[i]=cmb(A.count(A[i])-1)-l
for i in range(N):
  ans[i]+=k
  print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
import math
import sys
sys.setrecursionlimit(10**8)

fact_table = [-1] * (2*10**5)

def factorial(n):

    if n == 1:
        return 1
    if fact_table[n] != -1:
        return fact_table[n]
    else:
        temp = 1
        for i in range(n,0,-1):
            if fact_table[i] != -1:
                temp = temp * fact_table[i]
                break
            else:
                temp = temp * i

        fact_table[n] = temp
        return fact_table[n]


def combi(n,r):
    #階乗が多すぎる！　階乗テーブルだ！　×××メモリーエラーになる 違う！階乗の再帰によるメモリ不足だ！
    if n < r:
        return 0
    return factorial(n) // (factorial(r) * factorial(n-r))

def main():
    #2*10**5程度なら全てリストに収まる！
    #各数値の数をカウント！　k番目の数値だけ-1！
    #そして組み合わせ計算だ！nC2！
    n = int(input())
    num_counter = [0] + [0]*n #1-indexed!
    lst = [0]
    for i in [int(l) for l in input().split()]:
        t = i
        lst.append(t)
        num_counter[t] += 1

    answer_lst = [0]+[0] * n
    even_flag = [False]+[False] * n

    #answer_lst
    for i in range(1,n+1):
        answer_lst[i] = combi(num_counter[i],2)
        #even_flag[i] = (num_counter[i] % 2 == 0) and (num_counter[i] != 0)

    tmp = sum(answer_lst)

    for i in range(1,n+1):
        k = lst[i]
        answer = tmp
        answer -= answer_lst[k]
        answer += combi(num_counter[k]-1,2)
        print(answer)



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
import collections

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

_ = int(input())
ns = input().split(" ")
cs = collections.Counter(ns)

c = 0
for n in ns:
	for k, v in cs.items():
		if v==1:
			c += 0
		elif n==k:
#			c += math.factorial(v-2)
			c += combinations_count(v-1, 2)
		else:
#			c += math.factorial(v-1)
			c += combinations_count(v, 2)
	print(c)
	c = 0

Submission status: Time Limit Exceeded

Solution code:
import collections
from operator import mul
from functools import reduce
N = int(input())
A = list(map(int,input().split()))

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

for i in range(N):
    L = A[0:i]+A[i+1:N]
    c = collections.Counter(L)
    l = [i for i in c.values() if i != 1]
    ans = 0
    for j in l:
        ans += cmb(j,2)
    print(ans)

Submission status: Time Limit Exceeded

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

A_set = set(A)

def cmb2(n):
	result = n * (n - 1) / 2

	return int(result)

ans_d = {}
for a_s in A_set:
	#print(A.count(a))
	ans_d[str(a_s)] = A.count(a_s)

for a in A:
    #A_new = ans_d.copy()
    ans_d[str(a)] -= 1
    ans = 0
    #print(A_new)
    #print("="*10)
    for a_n in ans_d.values():
        if a_n <= 1:
            continue
        else:
            ans += cmb2(a_n)
    print(ans)
    ans_d[str(a)] += 1

Submission status: Time Limit Exceeded

Solution code:
import math
import copy
N = int(input())
A = list(map(int,input().split()))
A_dict = dict()
for i in range(N):
    if A_dict.get(A[i]) is not None:
        A_dict[A[i]] += 1
    else:
        A_dict[A[i]] = 1

# 各キーが選ばれたときの答えを求めてdict型で持っておく
ans = dict()
for K,V in A_dict.items():
    count = 0
    A_dict_2 = copy.deepcopy(A_dict) # 辞書をオリジナルからコピー,deepcopy
    A_dict_2[K] -= 1 # そのキーを取り出した想定
    for k,v in A_dict_2.items():
        if v >= 2:
            count += int(math.factorial(v)/(2*math.factorial(v-2)))
    ans[K] = count

for i in range(N):
    print(ans[A[i]])

Submission status: Time Limit Exceeded

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

for i in range(n):
    ans = 0
    ret = a.copy()
    ret.pop(i)
    c = Counter(ret).most_common()
    
    for j in c:
        if j[1] >= 2:
            ans += (j[1] * (j[1] - 1)) / 2

    print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
import math,collections

def f(c):
  sum=0
  for i in c:
    sum+=g(i,2)
  return sum

def g(n,r):
  if n==0 or n==1:return 0
  else:return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))

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

for i in range(n):
  l=k[0:i]
  l.extend(k[i+1:])
  c=collections.Counter(l).values()
#  print('l:',l,'c:',c)
  print(f(c))

Submission status: Time Limit Exceeded

Solution code:
import collections
import math

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

N = int(input())
A = list(map(int, input().split()))
Ay = list(set(A))
c = collections.Counter(A)
cnt = 0
ansx = []
ansy = []

for i in Ay:
    for x, y in c.items():
        if i == x and y >= 3:
            cnt += combinations_count(y - 1, 2)
        elif i != x and y >= 2:
            cnt += combinations_count(y, 2)
    ansx.append(i)
    ansy.append(cnt)
    cnt = 0

for i in A:
    print(ansy[ansx.index(i)])

Submission status: Time Limit Exceeded

Solution code:
import copy
from scipy.misc import comb
from collections import Counter

N=int(input())
A=list(map(int,input().split() ))
B=[-1]*N   #メモ化。iの時の方法の総数

f_cnt=Counter(A)
f_dic=dict(f_cnt)

for i,item in enumerate(A):
  if B[item-1]>-1:
    print(B[item-1])
  else:
    D=copy.deepcopy(f_dic)
    D[item] -= 1
    opt=0
    for item3 in D:
      if D[item3]>=2:
        opt += comb(D[item3],2,exact=True)
    B[item-1]=opt
    print(opt)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
li = list(map(int,input().split()))
for i in range(n):
    a=li.pop(i)
    ss=list(set(li))
    res=0
    for j in ss:
        co=li.count(j)
        if co>1:
           res+=co*(co-1)//2
    print(res)
    li.insert(i,a)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N = int(input())
A = list(map(int,input().split()))
c = Counter(A)

for a in A:
    sum = 0
    for i in c:
        if a ==i:
            n =c[i]-1
        else:
            n=c[i]
        sum += n * (n - 1) // 2
    print(sum)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
k = list(map(int, input().split()))
d = {}
for i in range(N):
    if k[i] in d:
        d[k[i]] += 1
    else:
        d[k[i]] = 1

for i in range(N):
    res = 0

    for key in d:
        if d[key]>1:
            if key == k[i]:
                res += (d[key]-1)*(d[key]-2)/2
            else:
                res += d[key]*(d[key]-1)/2
    print(int(res))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
P = list(map(int, input().split()))
set_of_numbers = set(P)
# num_dict = {}
# num_dict_k = {}
diff = {}
result_sum_all = 0
for num in set_of_numbers:
    num_of_num = P.count(num)
    pair_set = num_of_num*(num_of_num-1)
    pair_set_k = (num_of_num-1)*(num_of_num-2)
    # num_dict[num] = P.count(num)
    result_sum_all += pair_set
    diff[num] = pair_set_k - pair_set
    # num_dict[num] = int(pair_set)
    # num_dict_k[num] = int(pair_set_k)
    # print(pair_set, pair_set_k)


for k in range(N):
    # 取り除く数字はP[k]
    result = result_sum_all + diff[P[k]]# + num_dict_k[P[k]]
    print(int(result/2))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
a1 = sorted(a)
a1 = list(set(a1))
total = 0

for i in range(len(a1)):
  to = a.count(a1[i])
  total += (to*(to-1)//2)
  
for i in range(n):
  to = a.count(a[i])-1
  print(total-(to*(to+1)//2)+(to*(to-1)//2))

Submission status: Time Limit Exceeded

Solution code:
#from collections import Counter

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

ans = 0
for i in set(A_list):
    v = A_list.count(i)
    if v < 2:
        break
    ans += v*(v-1)/2

for k in range(N):
    tgt = A_list[k]
    n = A_list.count(tgt)
    print(int(ans - n + 1))

Submission status: Time Limit Exceeded

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

p = 7+pow(10,9)
def cmb(n,r,p):
    numerator = 1
    for i in range(n-r+1, n+1):
        numerator = numerator * i % p
    denominator = 1
    for i in range(1, r+1):
        denominator = denominator * i % p
    return numerator * pow(denominator, p-2, p) % p


b = list(set(a))

n_b = len(b)
c = []

for i in range(n_b):
    c.append(a.count(b[i]))

e = list(set(c))

d = 0

for i in range(len(e)):
    d += cmb(e[i], 2, p)*c.count(e[i])

for i in range(n):
    if a.count(a[i]) == 1:
        print(d)
    elif a.count(a[i]) == 2:
        print(d-1)
    else:
        print(d - cmb(a.count(a[i]), 2, p) + cmb(a.count(a[i])-1, 2, p))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding:utf-8 -*-

comb_dic = {}

def combination_formula_MOD(n, r, MOD):
    """nCrを O(min(n-r, r)) で高速に計算する"""
    def _inv(x, MOD):
        """xの逆元を返す"""
        return pow(x, MOD-2, MOD)
    if r > n: return 0

    if n in comb_dic:
        return comb_dic[n]

    r = min(n-r, r)
    bunsi, bunbo = 1, 1
    for i in range(r):
        bunsi = bunsi*(n-i)%MOD
        bunbo = bunbo*(i+1)%MOD

    ans = (bunsi*_inv(bunbo, MOD))%MOD
    comb_dic[n] = ans
    return ans


def combination_formula(n, r):
    """nCrは、O(min(n-r, r))で実装する
    Notes:
        分子と分母がかなり大きな値になった場合、計算は遅くなるので注意
        求める値がmodをとった値でいい場合、フェルマーの小定理を使った方法が速い。
    """
    if r > n: return 0

    if n in comb_dic:
        return comb_dic[n]

    r = min(n-r, r)
    bunsi, bunbo = 1, 1
    for i in range(r):
        bunsi = bunsi*(n-i)
        bunbo = bunbo*(i+1)

    comb_dic[n] = bunsi//bunbo
    return comb_dic[n]


def solve():
    N = int(input())
    As = list(map(int, input().split()))
    MOD = 10**9+7

    dic = {}
    for a in As:
        if not a in dic:
            dic[a] = 0
        dic[a] += 1

    ans_dic = {}  # すでに答えを計算したもの
    for a in As:
        if not a in ans_dic:
            ans = 0
            for key, value in dic.items():
                if key == a:
                    value -= 1
                ans += combination_formula(value, 2)
                # ans += combination_formula_MOD(value, 2, MOD)
            ans_dic[a] = ans
            print(ans_dic[a])
        else:
            print(ans_dic[a])


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
default=0
for i in set(a):
    default+=a.count(i)*(a.count(i)-1)//2
for k in a:
    print(default-(a.count(k)-1))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
l = list(map(int, input().split()))
dic = {}
ans = 0
a = 0

for i in range(n):
  a = l.count(i+1)
  if a != 0 or a != 1:
    dic[i+1] = a
    x = l.count(i+1)
    ans += int(x*(x-1)/2)
  
for i in range(n):
  if dic.get(l[i]) != None:
    a = dic[l[i]]
    print(ans-a+1)

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input())


def combination(n, r):
    if n >= 2:
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
    else:
        return 0

A = input().split()
len(set(A))
B = {}
C = {}
for i in set(A):
    B[i] = combination(A.count(i) - 1, 2)
    C[i] = combination(A.count(i), 2)
sC = sum(C.values())
for i in A:
    print(B[i] - C[i] + sC)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

u = list(np.unique(A))
c = []
sum = 0
for j in u:
    _ = len(np.where(A == j)[0])
    c.append(_)
    sum += int(_ * (_ - 1) / 2)

s = ""
for k in range(N):
    v = c[u.index(A[k])]
    s += str(sum - v + 1) + "\n"
print(s)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = list(map(int,input().split()))
total=[0]*n
k = []
for i in range(n):
    t = [0]*n
    for j in range(i+1,n):
        if A[i]==A[j]: t[j]=1
    k.append(t)
    total = list(map(sum, zip(total, t)))
for i in range(n):
    print(sum(total)-total[i]-sum(k[i]))