【ABC159 D】「Banned K」を解く【Python3】

abc159d

コンテスト一覧へ

 

整数Aiが書かれているボールN個に対して、条件に沿う答えをそれぞれ出力する問題です。

N個のボールから、書かれている整数が等しいボールを2つ選ぶ方法の数を、最初に計算してしまいます。

提出
import collections
n = int(input())
a = list(map(int, input().split()))

c = collections.Counter(a)
s = 0

for i in list(c.values()):
    s += i*(i-1) // 2

for i in a:
    print(s-(c[i]-1))

collectionsモジュールのCounter()を使用し、全ての要素の数を数えます。

import collections
l = ['a', 'a', 'a', 'b', 'c', 'c']
c = collections.Counter(l)
print(c)
# > Counter({'a': 3, 'c': 2, 'b': 1})

「ボールを2つ選ぶ方法の数」はボールの数をmとすると、「m×(m-1)/2」で求められるので、全ての整数において、その数を計算し足し合わせます。

「k番目のボールを除く」ということは、同じ整数が書かれているボールの数が1つ減ることになります。

1つ減った後の「整数が等しいボールを2つ選ぶ方法の数」は、下記のように求めることができます。

(m-1)×(m-2)/2 = m×(m-1)/2 - sabun

ここから

sabun = m-1

が求まります。

(例えば、5個から2個選ぶ方法は10通り、4個から2個選ぶ方法は6通りとなり、10通りから「5-1」を引いた数になっています)

最初に計算しておいた「整数が等しいボールを2つ選ぶ方法の数s」からこの「sabun」を引いた数をN個それぞれ出力します。

【ABC159】解説記事リスト

コンテスト一覧に戻る

コメントを残す

メールアドレスが公開されることはありません。