kmjp's blog

競技プログラミング参加記です

AtCoder ARC #009 : Python練習編

どんどん行きます。考えたらARC#008からはここで記事書いてるし、問題文とかは省略でいいか。
ということでPythonならではの事項があればそこだけ書いていく。
http://arc009.contest.atcoder.jp/assignments

C++で書いた時の記事はここ:
http://kmjp.hatenablog.jp/entry/2012/10/20/0900
http://kmjp.hatenablog.jp/entry/2012/10/20/0930


A - 元気にお使い!高橋君

物の値段と購入数に対し、消費税込価格を答える問題。
総額を出して1/20を足すだけ。

N=input()
r=0
for i in range(0,N):
	A,B=map(int,raw_input().split(" "))
	r += A*B

r = r + r/20
print(r)

B - おとぎの国の高橋君

数字の大きさが0以外変化したとき、数値集合を昇順に並べ替える。
以前文字列を反転させて辞書順に並べた問題あったけど、あれと同様に数値を順番に応じて変化させ、後で戻す。

B=map(int,raw_input().split(" "))
m1=range(0,10)
m2=range(0,10)
for i in range(0,10):
	m1[B[i]]=i
	m2[i]=B[i]

N=input()
A=[]
for i in range(0,N):
	c=input()
	v=0
	for d in range(0,10):
		v += m1[(c/(10**d))%10]*(10**d)
	A.append(v)

A.sort()
for i in A:
	v=0
	for d in range(0,10):
		v += m2[(i/(10**d))%10]*(10**d)
	print(v)

C - 高橋君、24歳

N人が互いに1人1つずつ手紙を出して1つ受け取るとき、K人が自分以外のを受け取る場合の数を答える。
K人が互いに自分以外の手紙を受け取る組み合わせ数D[K]=(K-1)*(D[K-1]+D[K-2])で、そこに{}_NC_Kを掛ければよい。
最初Combinationに使うAのmod mにおける逆元、(A^(m-2) )%mの演算を自力でやったけど、pow関数でmodも組み込めるのね。
速度は大差なかった。

N,K=map(int,raw_input().split(" "))
m=1777777777

def comb(p,q):
	r=1
	rr=1
	for v in range(0,q):
		r = (r*(p-v)) % m
		rr = (rr*(v+1)) % m
	
	return ((r*pow(rr,m-2,m)) % m)

P=comb(N,K)
pat=[0,0,1]
for i in range(3,K+1):
	pat.append((pat[i-1]*(i-1) + (i-1)*pat[i-2])%m)

P=(P*pat[K])%m
print(P)

まとめ

pow関数が使いやすくて良いね。