競技プログラミング

ABC159D Banned K

問題

https://atcoder.jp/contests/abc159/tasks/abc159_d

方針

  • ボールを除かない場合の選び出す方法をかぞえあげる
  • あるボールを除いた場合を考える
    • そのボールと同じ値が書かれているボールが全部でD個とした場合、そのボールを除くことでD-1通りの組み合わせが失われる。

ポイント

  • 要素の数え上げにはcollections.Counterを使う。
  • 「どの値のボールが何個あるか」は辞書にしておく。

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
import collections
def C(n):
    return n * (n-1) // 2
N = int(input())
A = list(map(int,input().split()))
c = collections.Counter(A)
d = {}
sm = 0
for k,v in c.most_common():
    d[k] = v
    sm += C(v)
for a in A:
    print (sm - d[a] + 1)

記事情報

  • 投稿日：2020年3月23日
  • 最終更新日：2020年3月23日