Solve Boot camp for Beginners.
** Thoughts ** It will not pass unless it is suppressed to about $ O (N) $, so it is not enough to calculate the combination for each $ k $. If you think about it for a moment, you can see that the combinations of different types of numbers are independent. For example, when the number of balls removed is 1, the sum of combinations other than 1 does not change. Now let's consider how the combination of the removed numbers changes. The combination of choosing 2 from $ n $ is $ \ frac {n (n-1)} {2} $, and the combination of choosing 2 from $ n-1 $ is $ \ frac {(n-1) (n-) 2)} {2} $, so if you take the difference, it will be $ n-1 $. After that, check the number with Counter and check the whole combination to calculate.
from collections import Counter
n = int(input())
a = list(map(int,input().split()))
c = Counter(a)
key = c.keys()
comb = 0
for i in key:
comb += (c[i]) * (c[i]-1) // 2 #Examine combinations of non-prohibited states
for i in a:
ans = comb - (c[i]-1) #a[i]Combination of states where
print(ans)
I was able to solve problems that I couldn't solve two months ago, and I felt growth. see you. As an aside, today there is Ada Koda.
Recommended Posts