kmjp's blog

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

AtCoder ARC #008 : Python練習編

ここから後半戦。
http://arc008.contest.atcoder.jp/assignments

A - たこ焼き買えるかな?

たこ焼きの値段は1個15円、10個セットは100円の時、指定した数のたこ焼きを買う最安値を求める。
10個単位のたこ焼きはセットで買い、残りは1個ずつ買う場合とセット買いの安い方を取ればよい。

N=input()
A=(N/10)*100 + min((N%10)*15,100)
print(A)

B - 謎のたこ焼きおじさん

作りたい文字列と、文字集合のキットが与えられる。文字列を作るのに必要な最少キット数を求める。
各文字について、作りたい文字に含まれる数をキット中の数で割って繰り上げればよい。

N,M=map(int,raw_input().split(" "))
name=list(raw_input())
kit=(raw_input())

a={}
b={}
for n in name:
	a[n] = a.get(n,0)+1
for k in kit:
	b[k] = b.get(k,0)+1

r = 0
for key in a:
	if b.get(key,0) == 0:
		r = -1
		break
	r = max(r, (a[key]+(b[key]-1))/b[key])

print(r)

C - THE☆たこ焼き祭り2012

N人の人がいて、各人はたこ焼きを投げる最高速および受け取りの最高速と位置が与えられる。
先頭の人が1秒に1個たこ焼きを生成するとき、全員に行きわたる最短時間を求める。
中身はダイクストラをガリガリやればよいだけ。

N=input()
A=[]
for i in range(N):
	A.append([map(int,raw_input().split(" ")),999999999999999.0])
	
A[0][1]=0.0
q=queue.PriorityQueue()
q.put((0.0,0))
vis=[0 for i in range(1001)]

while not q.empty():
	ct,cur=q.get()
	if vis[cur]>0:
		continue
	vis[cur]=1
	
	for i in range(N):
		if vis[i]>0:
			continue
		nd = A[cur][1] + (((A[cur][0][0]-A[i][0][0])**2+(A[cur][0][1]-A[i][0][1])**2)**0.5) / min(A[cur][0][2],A[i][0][3])
		if nd < A[i][1]:
			A[i][1]=nd
			q.put((nd,i))

A.sort(lambda x,y: cmp(x[1],y[1]))
ma=0.0
for i in range(1,N):
	ma=max(ma, A[i][1]+(N-1-i))

print(ma)

まとめ

最後のダイクストラ法の実装でpythonのPriorityQueueを知った。