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 sys import stdin
import math
import fractions

n = int(stdin.readline().rstrip())
a = [int(x) for x in stdin.readline().rstrip().split()]

for i in range(n):
    d = [0] * n
    for j in range(n):
        if i != j:
            d[a[j] - 1] += 1
    #print(d)
    result = 0
    for dd in d:
        if dd > 1:
            result += dd * (dd - 1) / 2
    print(int(result))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
nCr = {}
def cmb(n, r):
    if n >= 2:
        if n - r < r: r = n - r
        if r == 0: return 1
        if r == 1: return n

        numerator = [n - r + k + 1 for k in range(r)]
        denominator = [k + 1 for k in range(r)]

        for p in range(2,r+1):
            pivot = denominator[p - 1]
            if pivot > 1:
                offset = (n - r) % p
                for k in range(p-1,r,p):
                    numerator[k - offset] /= pivot
                    denominator[k] /= pivot

        result = 1
        for k in range(r):
            if numerator[k] > 1:
                result *= int(numerator[k])

        return result
    else:
        return 0

A = input().split()
len(set(A))
B = {}
C = {}
for i in set(A):
    B[i] = cmb(A.count(i) - 1, 2)
    C[i] = cmb(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 copy
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def D159():
    N = int(input())
    A = input().split()
    #sum = 0
    for i in range(0, N):
        sum = 0
        A_ = copy.deepcopy(A)
        del A_[i]
        num = list(set(A_))
        num = [ _ for _ in num if A_.count(_) > 1]
        for j in num: # 全部回したら、タイムアウト
            sum += combinations_count(A_.count(j), 2)
        print(sum)

if __name__ == "__main__":
    D159()

Submission status: Time Limit Exceeded

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())
x = list(map(int,input().split()))

for i in range(len(x)):
    sum = 0
    t = x.pop(0)
    c = collections.Counter(x)
    for k in list(set(x)):
        if c[k] >= 2:
            sum += combinations_count(c[k],2)
    print(sum)
    
    x.append(t)

Submission status: Time Limit Exceeded

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

b=[0]*N
for a in A:
    b[a-1]+=1
    
c=[0]*N
tmp=b
for i in range(N):
    c[i]+=tmp[i]*(tmp[i]-1)//2
    
for a in A:
    b[a-1]-=1
    print(sum(c)-c[a-1]+b[a-1]*(b[a-1]-1)//2)
    b[a-1]+=1

Submission status: Time Limit Exceeded

Solution code:
import math,collections

def f(c):
  sum=0
  for i in c.values():
    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()))
c=collections.Counter(k)

for i in range(n):
  c=collections.Counter(k)
  c[k[i]]-=1
  print(f(c))

Submission status: Time Limit Exceeded

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

from collections import Counter 
import math 

# res = [] # solution for each key in A
res_list = {} # solution for each value in A

# counter ver
A_c = Counter(A)
l = len(A_c)

def ncr(j):
  return math.factorial(j) // math.factorial(2) // math.factorial(j - 2) if j >= 2 else 0

# store ncr for each value 
combs = {k: ncr(v) for k, v in A_c.items()}

s = sum(combs.values())
  
for m in A_c.keys():
  cnt = combs[m]

  n = s
  n -= cnt # the only inaccurate entry
  n += ncr(A_c[m] - 1)
  res_list[m] = n

res = []
# for k in range(N):
#   res += '\n' + str(res_list[A[k]])
# print(res[1:])
for k in range(N):
  res.append(res_list[A[k]])
print('\n'.join([str(s) for s in res]))

Submission status: Time Limit Exceeded

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

for i in range(N):
    nums = {}
    B = A[:i] + A[i + 1:]
    for j in B:
        if not j in nums:
            nums[j] = 1
        else:
            nums[j] += 1
    count = 0
    for j in nums.values():
        count += j * (j - 1) // 2
    print(count)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
from collections import Counter
import sys
from functools import lru_cache

input = sys.stdin.readline

@lru_cache(maxsize=None)
def main():
    n = int(input().rstrip())
    l = list(input().rstrip().split())

    c = Counter(l)
    for item in l:
        ans = 0
        for key in c:
            tmp = c[key]
            if key == item:
                tmp -= 1
            ans += tmp * (tmp - 1) // 2
        print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

N=int(input())
A=list(map(int,input().split()))
B=list(set(A))
C=[]
D=[]
rireki=[]
for i in B:
    k=A.count(i)

    C.append(int((k-1)*(k-2)/2))
    D.append(int(k*(k-1)/2))
    rireki.append(i)

Dsum=sum(D)
rireki=[]
rirekinum=[]
for i in A:
    if not i in rireki:

        iindex=B.index(i)
        iindexnum=C[iindex]
        num=Dsum-D[iindex]
        ans=iindexnum+num
        rireki.append(i)
        rirekinum.append(ans)
        print(ans)
    else:
        num=rireki.index(i)
        print(rirekinum[num])

Submission status: Time Limit Exceeded

Solution code:
import collections
import math

#****************************************************************
def comb(n):
    if n < 2:
        return 0
    else:
        return math.factorial(n) // (math.factorial(n - 2) * math.factorial(2))
#****************************************************************

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

c = collections.Counter(A)
dict_ans = {i:0 for i in c.keys()}
full_ans = sum(list(map(comb, c.values())))

for i in c.keys():
    target = c.copy()
    target[i] -= 1
    if target[i] == 0:
        dict_ans[i] = full_ans
    else:
        dict_ans[i] = sum(list(map(comb, target.values())))

for i in A:
    print(dict_ans[i])

Submission status: Time Limit Exceeded

Solution code:
import math
import collections

def main():
    ansdic={}
    n = int(input())
    num_list = list(map(int, input().split()))  
    for i in range(len(num_list)):
        if i in ansdic:
          print(ansdic[i])
       	else:
          pop = num_list.pop(i)
          dic = collections.Counter(num_list)
          for k, j in dic.items():
              if j < 2:
                pass
              else:
                ansdic[k] = int(j * (j-1)/2)
          print(sum(ansdic.values()))
          ansdic = {}
          num_list.insert(i, pop)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


samelist = [[0] * N for i in range(N)]
for i in range(N):
    number = 0
    for j in range(i+1, N):
        if A[i] == A[j]:
            samelist[i][j] = 1
same = np.array(samelist)
sum = np.sum(same)

for k in range(N):
    print(sum-np.sum(same, axis=0)[k]-np.sum(same, axis=1)[k])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math
def comb(n,r):
    if n - r < 0:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def choose_ball(num, nums):
    count = 0
    for i in nums:
        if num == i:
            count += comb(nums[i]-1,2)
        else:
            count += comb(nums[i],2)
    return count

N = int(input())
A = list(map(int,input().split()))
nums = {}
for num in A:
    if not num in nums:
        nums[num] = 1
    else: 
        nums[num] += 1
for num in A:
    print(choose_ball(num, nums))

Submission status: Time Limit Exceeded

Solution code:
from math import factorial
import collections

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

L = collections.Counter(A)

L = L.most_common()

for k in range(N):
    c = 0
    x = A[k]
    for z in L:
        if z[0] == x:
            if z[1]-1 >= 2:
                c += factorial(z[1]-1) // factorial(2) // factorial(z[1]-1 - 2)
        else:
            if z[1] >=2:
                c += factorial(z[1]) // factorial(2) // factorial(z[1] - 2)
    print(c)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-

n = int(input())
a_list = list(map(int, input().split()))
aa_dict = {}
a_dict = {}
for a in a_list:
    if a in aa_dict:
        aa_dict[a] += 1
        if aa_dict[a] == 2:
            a_dict[a] = 2
        else:
            a_dict[a] += 1
    else:
        aa_dict[a] = 1
a_cal_dict = {}
cal_dict = {}
tokusyu = 0
for a in a_list:
    if a in a_cal_dict:
        print(a_cal_dict[a])
    else:
        if a in a_dict:
            ans = 0
            for key in a_dict:
                n = 0
                if key == a:
                    n = a_dict[key] - 1
                else:
                    n = a_dict[key]
                if n < 2:
                    continue
                if n in cal_dict:
                    ans += cal_dict[n]
                else:
                    cal_dict[n] = n * (n-1) // 2
                    ans += cal_dict[n]
            print(ans)
            a_cal_dict[a] = ans
        else:
            if 0 < tokusyu:
                print(tokusyu)
            else:
                for key in a_dict:
                    n = 0
                    if key == a:
                        n = a_dict[key] - 1
                    else:
                        n = a_dict[key]
                    if n < 2:
                        continue
                    if n in cal_dict:
                        tokusyu += cal_dict[n]
                    else:
                        cal_dict[n] = n * (n-1) // 2
                        tokusyu += cal_dict[n]
                print(tokusyu)
                a_cal_dict[a] = tokusyu

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=[int(x) for x in input().split()]
A_s=list(dict.fromkeys(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:
import copy
import collections
import math
N = input()
N = int(N)
A = list(map(int, input().split()))

def comb(n, r):
    if (n-r) >= 0:
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
    else:
        return 0
for num in A:
    ans=0
    c = collections.Counter(A)
    c[num] = c[num]-1
    for j in c.values():
        ans += comb(j,2)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

n = int(input())

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

ans_dict = {}
value_dict = {1: 0}
for i in range(n):
    num = a_list[i]
    if num in ans_dict.keys():
        print(ans_dict[num])
    else:
        c = Counter(a_list[:i] + a_list[i+1:])

        tmp_ans = 0
        for value in c.values():
            if value in value_dict.keys():
                tmp_ans += value_dict[value]
            else:
                tmp = int((value * (value - 1))/2)
                tmp_ans += tmp
                value_dict[value] = tmp
        ans_dict[num] = tmp_ans
        print(tmp_ans)

Submission status: Time Limit Exceeded

Solution code:
size = int(input())
values = list(map(int, input().split()))
skip_map = {}
count_map = {}
count_map_2 = {}

# 先に各数値とその存在数をカウントしておく
for i in range(size):
    if str(values[i]) in count_map:
        count_map[str(values[i])] = count_map[str(values[i])] + 1
    else:
        count_map[str(values[i])] = 1

for key in count_map.keys():
    value = count_map[key]
    if str(value) in count_map_2:
        count_map_2[str(value)].append(key)
    else:
        count_map_2[str(value)] = [key]


for i in range(size):
    if str(values[i]) in skip_map:
        print(skip_map[str(values[i])])
        continue
    check_int = count_map[str(values[i])]
    checks = count_map_2[str(check_int)]
    for check in checks:
        if str(values[i]) in skip_map:
            print(skip_map[str(values[i])])
            skip_map[str(values[i])] = result
            break
    else:
        # 集計
        calc_map = {}
        for j in range(size):
            if i == j:
                continue
            if str(values[j]) in calc_map:
                calc_map[str(values[j])] = calc_map[str(values[j])] + 1
            else:
                calc_map[str(values[j])] = 1
        # パターン
        result = 0
        for val in calc_map.keys():
            if 1 < calc_map[val]:
                for k in range(calc_map[val]):
                    result = result + k
        print(result)
        skip_map[str(values[i])] = result

Submission status: Time Limit Exceeded

Solution code:
import math


def kumiawase(n):
    if n == 0 or n == 1:
        return 0
    return math.floor(math.factorial(n) / math.factorial(n - 2) / 2)


n = int(input())
aL = list(map(int, input().split(" ")))

d = {}

for ai in aL:
    if ai in d:
        d[ai] += 1
    else:
        d[ai] = 1

for ai in aL:
    sm = 0
    for dk, di in d.items():
        if dk == ai:
            sm += kumiawase(di - 1)
        else:
            sm += kumiawase(di)
    print(sm)

Submission status: Time Limit Exceeded

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

	return result

if __name__ == "__main__":

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

	A_set = set(A)

	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(int(ans))
		ans_d[str(a)] += 1

Submission status: Time Limit Exceeded

Solution code:
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()))
cnt={}
comb={}
ans=0
for i in a:
    if i in cnt:
        cnt[i]+=1
    else:
        cnt[i]=1
        
for i in cnt.values():
    if i<2:
        continue
    if not i in comb:
        comb[i]=combinations_count(i,2)
    ans+=comb[i]

for i in range(n):
    pans=ans
    if cnt[a[i]] in comb:
        pans-=comb[cnt[a[i]]]
    c=cnt[a[i]]-1
    if c>1:
        if not c in comb:
            comb[c]=combinations_count(c,2)
        pans+=comb[c]
    print(pans)

Submission status: Time Limit Exceeded

Solution code:
import copy
import math

p_dict = {}
def permutation_count(x):
    ret = 0
    if x == 2:
        ret = 1
    elif 2 < x:
        if(not x in p_dict.keys()):
            ret = math.factorial(x) // (2*(math.factorial(x-2)))
        else:
            ret = p_dict[x]

    return ret

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

unique_a = set(a)

cnt_all_conbi = 0
a_cnt_dict = {}

for i in unique_a:
    x = a.count(i)
    a_cnt_dict[i] = x
    cnt_all_conbi += permutation_count(x)

for i in a:
    x = a_cnt_dict[i]
    print(cnt_all_conbi - (x-1))

Submission status: Time Limit Exceeded

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

from copy import deepcopy
import math
import collections
import sys


def LI():
    return list(map(int, sys.stdin.buffer.readline().split()))


def I():
    return int(sys.stdin.buffer.readline())


def LS():
    return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()


def S():
    return sys.stdin.buffer.readline().rstrip().decode('utf-8')


def IR(n):
    return [I() for i in range(n)]


def LIR(n):
    return [LI() for i in range(n)]


def SR(n):
    return [S() for i in range(n)]


def LSR(n):
    return [LS() for i in range(n)]


def SRL(n):
    return [list(S()) for i in range(n)]


def MSRL(n):
    return [[int(j) for j in list(S())] for i in range(n)]

# ----------------------------------------------------------------


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


def main():
    n = I()
    ball = LI()
    def_ans = {}
    ans_list = {}

    c = collections.Counter(ball)
    # c_nums = c.values()

    for key, val in c.items():
        if val >= 2:
            def_ans[key] = combinations_count(val, 2)
        else:
            def_ans[key] = 0

    for i in ball:
        if i in ans_list:
            print(ans_list[i])
            continue
        else:
            ans = 0
            # def_ans_temp = deepcopy(def_ans)
            for key, val in def_ans.items():
                if key == i and c[i] >= 3:
                    ans += val * (c[i] - 2) / (c[i])
                elif key == i and c[i] < 3:
                    continue
                else:
                    ans += val

            ans_list[i] = int(ans)
            print(int(ans))


main()

# def main():
#     n = I()
#     ball = LI()
#     ans = []

#     for i in range(n):
#         ans = 0
#         ball_temp = deepcopy(ball)
#         ball_temp.pop(i)
#         c = collections.Counter(ball_temp)
#         c_nums = c.values()

#         for p in c_nums:
#             if p >= 2:
#                 ans += combinations_count(p, 2)

#         print(ans)

# main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N = int(input())
li = list(map(int, input().split()))
for k in range(N):
    check_li, ans = li[:k]+li[k+1:], 0
    counter = Counter(check_li)
    for i in counter.most_common():
        cnt = i[1]
        ans += cnt * (cnt-1) // 2
    print(ans)

Submission status: Time Limit Exceeded

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:
        gokei += 0
        sa.append(0)
    elif x ==2:
        gokei += 1
        sa.append(1)
    else:
        z = math.factorial(x)//(math.factorial(x-2)*math.factorial(2))
        gokei += z
        sa.append(z-z*(x-2)//x)

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

Solution code:
import collections
import math

n = int(input())

a = input().split()

for k in range(n):
    if k == 0:
        l = a[1:n]
    elif k == n-1:
        l = a[0:n-1]
    else:
        l = a[:k] + a[k+1:n]

    c = collections.Counter(l)
    u = list(c.values())
    cnt = 0
    for i in range(len(u)):
        if not u[i] == 1:
            cnt += math.factorial(u[i])/math.factorial(u[i]-2)/math.factorial(2)
    print(int(cnt))

Submission status: Time Limit Exceeded

Solution code:
import collections

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import collections


def solve(N: int, A: "List[int]"):
    for k in range(len(A)):
        a = A[:]
        del a[k]
        c = collections.Counter(a)
        values, counts = zip(*c.most_common())
        ans = 0
        for i in counts:
            ans += int(i * (i-1) / 2)
        print(ans)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
@lru_cache(maxsize=1024)
def nC2(n):
    return n * (n-1)//2

N=int(input())
A=list(map(int, input().split()))
Y = set(A)
memo = {}
Z = set()
#数え上げ
str_count = {}
for i in Y:
    str_count[i] = A.count(i)
    if str_count[i] != 1:
        Z.add(i)
for k in range(0,N):
    key = A[k]
    if key in memo:
        print(memo[key])
        continue
    c = 0
    for i in Z:
        if i == A[k]:
            c += nC2(str_count[i] - 1)
        else:
            c += nC2(str_count[i])
    memo[key] = c
    print(c)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

def cc(c):
    if c<2: return 0
    return int(c*(c-1)/2)

n=int(input())
a=[int(A) for A in input().split()]

ball_cnt = dict(Counter(a))
for k in range(n):
    cnt=0
    for key, value in ball_cnt.items():
        if a[k]==key:
            cnt+=cc(value-1)
        else:
            cnt+=cc(value)
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a = list(map(int,input().split()))
for i in range(n):
  cnt=0
  for j in range(n-1):
    if i==j:
        continue
    for k in range(j+1,n):
      if i==k:
        continue
      elif a[j]==a[k]:
        cnt+=1
  print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
lis = list(map(int, input().split()))
for x in range(N):
  lis_ = [lis[i] for i in range(N) if i != x]
  c = 0
  for i in range(N-2):
    lis_i = [lis_[j] for j in range(i+1, N-1) if lis_[i] == lis_[j]]
    c+= len(lis_i)
  print(c)

Submission status: Time Limit Exceeded

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

z = []
for i in range(len(a3)):
     z.append(a.count(a3[i]))

for j in range(n):
    count = 1
    count += sum(list(map(lambda x:int(x*(x-1)/2) ,z)))
    count -= z[a3.index(a[j])]
    print(int(count))

Submission status: Time Limit Exceeded

Solution code:
import collections
N = int(input())
A = list(map(int, input().split()))
for x in range(N):
  ans = 0
  b = A.pop(x)
  c = collections.Counter(A)
  v = [k for j,k in c.items()]
  for i in v:
    ans += int(i*(i-1)/2)
  print(ans)
  A.insert(x,b)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n = int(input())

a = np.array([i for i in list(map(int, input().split()))])
d = {}
s = {}

for i in sorted(set(a)):
  d[i] = len(a[a==i])
  
sum = 0
for i in d:
  k = d[i]
  if k>1:
    sum += (k*(k-1))//2

for i in range(n):
  nd = d[a[i]]
  ans = sum-(nd*(nd-1))//2
  nd -= 1
  if nd>1:
    ans += (nd*(nd-1))//2
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
import collections

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

for k in range(1,N+1):
    n = 0
    B_list = copy.copy(A_list)
    del B_list[(k-1)]
    c = collections.Counter(B_list)

    for i in c.values():
        if i >= 2:
            n += i*(i-1)/2
    print(int(n))

Submission status: Time Limit Exceeded

Solution code:
import collections
from scipy.misc import comb
n = int(input())
a = list(map(int,input().split()))
for i in range(len(a)):
  o = 0
  b = a[:]
  del b[i]
  c = collections.Counter(b)
  n = len(set(b))
  for i in c.values():
    o += comb(i,2,exact=True)
  print(o)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
n = int(input())
lst = list(map(int, input().split()))
sett = set(lst)

if len(lst) == len(sett):
    for i in range(n):
        print(0)
elif len(sett) == 1:
    for i in range(n):
        print(len(list(combinations(range(n-1), 2))))
else:
    newLst = []
    for x in sett:
        newLst.append(lst.count(x))
    dic = dict(zip(sett, newLst))
    for i in range(n):
        summ = 0
        dic[lst[i]] = dic[lst[i]]-1
        for x in list(dic.values()):
            if x < 2:
                pass
            elif x == 2:
                summ = summ + 1
            else:
                summ = summ + len(list(combinations(range(x), 2)))
        dic[lst[i]] = dic[lst[i]]+1
        print(summ)

Submission status: Time Limit Exceeded

Solution code:
import math

def resolve():
    n = int(input())
    a = [int(x) for x in input().split()]

    for k in range(n):
        # 初期化
        ak = a[:] # deep copy
        del ak[k]
        kumi = 0
        ended = set()

        # loop
        for a0 in ak:
            if a0 in ended:
                continue
            cnt = ak.count(a0)
            if cnt >= 2:
                kumi += kumiawase(cnt ,2)
            ended.add(a0)
        print(kumi)

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

resolve()

Submission status: Time Limit Exceeded

Solution code:
import copy
import numpy as np
from math import factorial

def num_choice_2(N):
    if N > 1:
        return N * (N - 1) // 2
    else:
        return 0

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

nums = np.zeros(N, dtype=int)
for a_i in A:
    nums[a_i - 1] += 1

comb_default = np.array([num_choice_2(x) for x in nums])
comb_selected = np.array([num_choice_2(x - 1) for x in nums])

for i in range(N):
    ans = comb_selected[A[i] - 1]
    ans += np.sum(comb_default[:A[i] - 1]) + np.sum(comb_default[A[i]:])

    print(ans)

Submission status: Time Limit Exceeded

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

d = {}

sm = 0
for i in a:
    if i not in d:
        ac = a.count(i)
        bc = ac -1
        d[i] = (ac*(ac-1))/2 - (bc*(bc-1))/2
        sm += (ac*(ac-1))/2

 
for j in a:
    print sm-d[j]

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce
 
import copy
import sys
input = sys.stdin.readline
 
def combinations(n, r):
    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
 
N = int(input())
 
AList = list(map(int, input().split()))

SortList = copy.copy(AList)
SortList.sort()
 
NumberList = []
CountList = []
tmp = SortList[0]
count = 0
for i in SortList:
    if tmp == i:
        count += 1
    else:
        NumberList.append(tmp)
        CountList.append(count)
        tmp = i
        count = 1
NumberList.append(tmp)
CountList.append(count)
 
CountListCopy = copy.copy(CountList)
 
result = 0
for i in range(0, len(AList)):
    CountListCopy[NumberList.index(AList[i])] -= 1
    for q in CountListCopy:
        if q < 2:
            continue
        else:
            result += combinations(q, 2)
    print(result)
    result = 0
    
    CountListCopy = copy.copy(CountList)

Submission status: Time Limit Exceeded

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)
total_ans = 0
for k, v in c.items():
    if v > 1:
        total_ans += combinations_count(v, 2)

for k_ball in A:
    if c[k_ball] > 2:
        print(
            total_ans
            - (combinations_count(c[k_ball], 2) - combinations_count(c[k_ball] - 1, 2))
        )
    elif c[k_ball] > 1:
        print(total_ans - 1)
    else:
        print(total_ans)

Submission status: Time Limit Exceeded

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

def combinations_count2(n, r):
    if n < 2:
        return 0
    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

c = collections.Counter(A)

dic = {}
for i in c:
    dic[i]= [combinations_count2(c[i], 2), combinations_count2(c[i] - 1, 2)]

for ai in A:
    ans = 0
    for i in dic:
        if i == ai:
            ans += dic[i][1]
        else:
            ans += dic[i][0]
    print(ans)

Submission status: Time Limit Exceeded

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

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

def factorial(n):
    #fact_tableが機能してない！？

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

                break
            else:
                append_counter += 1
                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
def comb2(t):
    if t <= 1:
        return 0
    else:
        return math.factorial(t) // (math.factorial(t - 2) * math.factorial(2))
n = int(input())
nl = input().split()
nd = {}
for num in nl:
    if num not in nd.keys():
        nd[num] = 0
    nd[num] +=1
for i in nl:
    ans = 0
    for k, v in nd.items():
        if k == i:
            ans += comb2(int(v)-1)
        else:
            ans += comb2(int(v))
    print(ans)