【ABC200 C】「Ringo’s Favorite Numbers 2」を解く【Python3】

コンテスト一覧へ

 

200という整数が大好きなりんごさんのために、与えられた条件をすべて満たす整数組の個数を求める問題です。

提出
import collections

n = int(input())
a = list(map(int, input().split()))

m = [i%200 for i in a]
c = collections.Counter(m)
ans = 0

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

print(ans)

入力はすべて整数です。

Ai-Aj が200の倍数である、ということは、「Ai,Aj をそれぞれ200で割った余りが同じである」ということと等しいです。

例えば、入力例1にある、123と523の差は200の倍数であり、それぞれ200で割った余りも同じになります。

200で割った余りが異なる整数同士の差が200の倍数になることはありえません。

ということで、数列Aのすべての整数を200で割ったリストを作り、余りが同じものの組み合わせを計算していきます。

リスト内の同じ要素の個数を数えるやり方はいくつかありますが、今回はcollectionsモジュールを使用しています。

これは、以下のようにリスト内の要素を数え上げます。

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

辞書型として扱うことができ、キーと要素をそれぞれ取り出すことができます。

print(c.keys())                # > dict_keys(['a', 'b', 'c'])
print(c.values())              # > dict_values([4, 1, 2])

 

最後のfor文で、組み合わせの数を計算しています。

同じものがx個あったときの組み合わせの数は、xC2 で求められるため

x*(x-1)/2

となります。

【ABC200】解説記事リスト

コンテスト一覧に戻る

コメントを残す

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