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!
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! !! !!
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 ...
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)
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!
Recommended Posts