Résoudre ABC159-D en Python

introduction

Résolvez le camp d'entraînement pour les débutants.

** Pensées ** Il ne passera que s'il est supprimé à environ $ O (N) $, il ne suffit donc pas de calculer la combinaison pour chaque $ k $. Si vous y réfléchissez un instant, vous pouvez voir que les combinaisons de différents types de nombres sont indépendantes. Par exemple, lorsque le nombre de balles retirées est de 1, la somme des combinaisons autres que 1 ne change pas. Voyons maintenant comment la combinaison de nombres supprimés change. La combinaison pour choisir 2 parmi $ n $ est $ \ frac {n (n-1)} {2} $, et la combinaison pour choisir 2 parmi $ n-1 $ est $ \ frac {(n-1) (n-) 2)} {2} $, donc si vous prenez la différence, ce sera $ n-1 $. Après cela, vérifiez le nombre avec Counter et vérifiez la combinaison entière pour calculer.

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 #Examiner les combinaisons d'états non interdits

for i in a:
    ans = comb - (c[i]-1) #a[i]Combinaison d'états où
    print(ans)

Résumé

J'ai pu résoudre des problèmes que je ne pouvais pas résoudre il y a deux mois et j'ai ressenti une croissance. à plus. En passant, il y a aujourd'hui Ada Koda.