【Python】ABC159D(高校数学nCr)【AtCoder】

競プロはノートとペンを用意してやろう！！！
(特に数学の式が出てきたら)

ABC159D

Difficulty:417
今回は解説の解説をしますw
まずは解説より引用。

①N個のボールから、書かれている整数が等しいような異なる2つのボールを選び出す方法の数
②k番目のボールを除いたN−1個のボールから、k番目のボールと同じ整数が書かれたボールを選び出す方法の数
をそれぞれ求めて、前者から後者を引けば求まります。
前者は、∑Ni=1(ci 2), 後者はcAk−1となります。

後者は「cAk−1」となります。
なんでやねん！

後者は「cAk−1」となります。の意味

こういうときは具体例を考えて法則性を見つける（ノートとペンがないと無理！）
＜具体例1＞
5個から２個選ぶ→5C2=5*4/2*1=10通り！
4個から２個選ぶ→4C2=4*3/2*1=6通り！
　⇨10-6=4通り減る！
確かにcAk−1=5-1=4通り減ってるね。
＜具体例2＞
6個から２個選ぶ→6C2=6*5/2*1=15通り！
5個から２個選ぶ→5C2=5*4/2*1=10通り！
　⇨15-10=5通り減る！
確かにcAk−1=6-1=5通り減ってる！
＜具体例３＞
7個から２個選ぶ→7C2=7*6/2*1=21通り！
6個から２個選ぶ→6C2=6*5/2*1=15通り！
　⇨21-15=6通り減る！
確かにcAk−1=7-1=6通り減ってる！！！

実際の競技中は早くACを出すために、法則性が確信にかわり次第プログラムの実装を始めてもいいと思う。
一応nの場合も気になるので試してみる・・・

＜具体例n＞
n個から２個選ぶ→nC2=n*(n-1)/2*1
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」

なるほど・・・
ノートとペンは大事！！！

実際の回答

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:
    print(sum-(count[x]-1))

案外と少ないソース量でした・・・

別解

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)

階乗は安易に使用禁止！

nC2の計算を階乗を使ってやろうとした人はいないよね
俺です
階乗math.factorial()はでかい数字(今回の上限2*10^5)に耐えられません！！！TLE連発します！！！
俺はmath.factorial()を使ってPyPyで無理やりACもぎとりました。

#ダメ絶対。
math.factorial(x)//((math.factorial(x-2))*(math.factorial(2)))

おわり！