わかさぎのブログ

プログラミング、Atcoderの勉強とか

AtCoder Beginner Contest 081 C - Not so Diverse

Python Atcoder ABC 
N,K=map(int,input().split())
a=list(map(int,input().split()))

buk=[0 for i in range(1,200001)]
for i in a: buk[i]+=1

count=0
for i in buk:
    if i!=0:
        count+=1

buk=[i for i in buk if i>0]

delete=count-K
if delete<=0:
    print(0)

else:
    div=sorted(buk)
    div=div[:delete]
    suma=sum(div)
    print(suma)

考え方

バケットを利用する。
buk[i]:=数字iがbuk[i]個ある。
はじめはbuk[i]を0で初期化して、anの情報を突っ込む。
そうして0でないものの個数をカウントしてそれが数字の種類。
Ｋを上回っている分だけ種類を減らせばいいから、個数の少ない文字を消せばいい。
buk[i]から0を除外して小さい順にソートしてできた数列を使って、Kを上回っている分だけの項の和を取ればよい。

AtCoder Beginner Contest 200 C - Ringo's Favorite Numbers 2

連想配列 Atcoder ABC Python

コード

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

mod=200

b=[i%200 for i in a]

from collections import defaultdict

di=defaultdict(int)
for i in b:
    di[i]+=1

result=0
for i in range(200):
    n=di[i]
    result+=n*(n-1)//2

print(result)

考え方

200で割ったあまりで分類する。 a-bが200で割り切れるということはa≡b(mod200)であるから、数列anの中から200で割ったものの等しいものの集まりが何個あるか数えればいい。
例えば200で割ったあまりが2のものが3個なら3C2=n(n-1)/2をすればよく、それをすべて加算すればよい。

AtCoder Beginner Contest 058 C - 怪文書

連想配列 Python Atcoder ABC

コード

from collections import defaultdict

N=int(input())
s=[]
for i in range(N):
    tmp=list(input())
    s.append(tmp)

data=[]
for i in s:
    tmp=defaultdict(int)
    for j in i: tmp[j]+=1
    data.append(tmp)

setset=[set() for i in range(len(data))]
for i,j in zip(data,setset):
    for k in i.keys(): j.add(k)

common_set=setset[0]
for i in range(1,N):
    common_set=common_set & setset[i]

common=list(common_set)

countcount=[]
for i in common:
    count=100
    for j in data:
        count=min(count,j[i])
    countcount.append(count)

moji=""
for i,times in zip(common,countcount):
    for j in range(times):
        moji+=i

print("".join(sorted(moji)))

考え方

文字列S_iそれぞれについてdefaultdictで何の文字が何文字あるかの辞書を作る。
setの積集合を取って、S_iに共通な文字を抽出。
共通な文字それぞれについて、含む数の最小値を求める。

AtCoder Beginner Contest 073 C - Write and Erase

Atcoder ABC Python 連想配列

コード

from collections import defaultdict

N=int(input())
a=[]
for i in range(N):
    tmp=int(input())
    a.append(tmp)

di=defaultdict(int)

for i in a:
    di[i]=1-di[i]

count=0
for k,v in di.items():
    if v==1:
        count+=1

print(count)

考え方

defaultdictを使う。
初めて登場するなら0が返ってくる。
a=1-aとすることで、0なら1が、1なら0が返ってくるようにしている。

AtCoder Beginner Contest 082 C - Good Sequence

Atcoder ABC 鹿本 Python 連想配列 
from collections import defaultdict

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

di=defaultdict(int)

for i in a: di[i]+=1

lost=0
for key,kosu in di.items():
    #print(key,kosu)

    if kosu<key:
        lost+=kosu
    elif kosu==key:
        pass
    else:
        lost+=(kosu-key)


print(lost)