Löse ABC159-D in Python

Einführung

Löse das Bootcamp für Anfänger.

** Gedanken ** Es wird nicht bestanden, es sei denn, es wird auf ungefähr $ O (N) $ unterdrückt, daher reicht es nicht aus, die Kombination für jedes $ k $ zu berechnen. Wenn Sie einen Moment darüber nachdenken, können Sie sehen, dass die Kombinationen verschiedener Arten von Zahlen unabhängig sind. Wenn beispielsweise die Anzahl der entfernten Bälle 1 beträgt, ändert sich die Summe der anderen Kombinationen als 1 nicht. Betrachten wir nun, wie sich die Kombination der entfernten Zahlen ändert. Die Kombination zur Auswahl von 2 aus $ n $ ist $ \ frac {n (n-1)} {2} $, und die Kombination zur Auswahl von 2 aus $ n-1 $ ist $ \ frac {(n-1) (n-) 2)} {2} $. Wenn Sie also die Differenz nehmen, ist dies $ n-1 $. Überprüfen Sie danach die Zahl mit Counter und überprüfen Sie die gesamte zu berechnende Kombination.

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 #Untersuchen Sie Kombinationen nicht verbotener Zustände

for i in a:
    ans = comb - (c[i]-1) #a[i]Kombination von Zuständen wo
    print(ans)

Zusammenfassung

Ich konnte Probleme lösen, die ich vor zwei Monaten nicht lösen konnte, und ich spürte Wachstum. wir sehen uns. Nebenbei bemerkt gibt es heute Ada Koda.