AtCoder Beginner Contest 159 [ D - Banned K ]をPythonで解く（400点、🟫茶diff）

問題

atcoder.jp

解法

defaultdictを使って、数列Aの数値の出現回数をカウント。
Aの各数値の組み合わせ数nCrも計算してa_tmpに保存。

組み合わせ数の公式nCrを、真面目に計算してしまうと計算量が多くてTLEになってしまう。
問題は２つのボールを選び出す方法を求めよとのことなので、r = 2。
よって、
nC2 = n*(n-1)//2
で求まる。

あとは、k番目のボールを除いたときの1個引いたボール数との差分を計算して表示すればOK。

実装

参考

blog.hamayanhamayan.com

C(個数,2)、つまり、個数×(個数 - 1)/2の総和を取れば答えになる。