[Python] ABC159D (High School Mathematics nCr) [At Coder]

Let's prepare a notebook and a pen for the competition pro! !! !! (Especially when mathematical formulas come out)

ABC159D Difficulty:417 This time I will explain the explanation w First, quoted from Explanation.

① Number of methods to select two different balls with the same written integer from N balls (2) Number of methods for selecting a ball with the same integer as the k-th ball from the N-1 balls excluding the k-th ball. Can be obtained by subtracting the latter from the former. The former is ∑Ni = 1 (ci 2), and the latter is cAk-1.

** The latter is "cAk-1". ** ** why!

The latter is "cAk-1". Meaning of

In such a case, think of a concrete example and find the law (it is impossible without a notebook and a pen!)
Specific example 1
Choose 2 out of 5 → 5C2 = 5 * 4/2 * 1 = 10 ways! Choose 2 out of 4 → 4C2 = 4 * 3/2 * 1 = 6 ways! ⇨ 10-6 = 4 ways to reduce! Certainly cAk−1 = 5-1 = 4 ways have decreased.
Specific example 2
Choose 2 out of 6 → 6C2 = 6 * 5/2 * 1 = 15 ways! Choose 2 out of 5 → 5C2 = 5 * 4/2 * 1 = 10 ways! ⇨ 15-10 = 5 ways to reduce! Certainly cAk−1 = 6-1 = 5 ways have decreased!
Specific example 3
Choose 2 out of 7 → 7C2 = 7 * 6/2 * 1 = 21 ways! Choose 2 out of 6 → 6C2 = 6 * 5/2 * 1 = 15 ways! ⇨ 21-15 = 6 ways to reduce! Certainly cAk−1 = 7-1 = 6 ways have decreased! !! !!

In order to get AC quickly during the actual competition, I think it is okay to start implementing the program as soon as the rules change to conviction. I'm worried about n, so I'll give it a try ...

Specific example n
Select 2 out of n → nC2 = n * (n-1) / 2 * 1 Select 2 out of n-1 → (n-1) C2 = (n-1) * (n-2) / 2 * 1 n*(n-1)/2　- (n-1)*(n-2)/2 =( (n^2-n) - (n^2-3n+2) )/2 =(2n-2)/2

=「n-1」

I see··· Notebooks and pens are important! !! !!

Actual answer

test.py

import collections
def I(): return int(input())
def LI(): return list(map(int,input().split()))
N = I()
A = LI()
count = collections.Counter(A) #This is like a dictionary
sum = 0
for x in count.values():
    sum += x*(x-1)//2
for x in A:
    print(sum-(count[x]-1))

The amount of sauce was unexpectedly small ...

Another solution

test.py

import collections
def I(): return int(input())
def LI(): return list(map(int,input().split()))
N = I()
A = LI()
count = collections.Counter(A)
sum = 0
for x in count.values():
    sum += x*(x-1)//2
for x in A:
    temp = count[x]
    minus = temp*(temp-1)//2
    plus = (temp-1)*(temp-2)//2
    print(sum-minus+plus)

Factorial is not easily used!

No one tried to calculate nC2 using factorial, right? ~~ I am ~~ Factorial math.factorial () can't stand the huge numbers (upper limit 2 * 10 ^ 5 this time)! !! !! TLE will be fired! !! !! ~~ I used math.factorial () to force PyPy to strip AC. ~~

python

#Absolutely no.
math.factorial(x)//((math.factorial(x-2))*(math.factorial(2)))

end!