AtCoder ABC #035 : Python練習編

今回は不参加。PyPyがサポートされたおかげでPythonで通せる問題が増えました。
http://abc035.contest.atcoder.jp/assignments

A - テレビ

比率を確認するだけ。

W,H=map(int,raw_input().strip().split(" "))

if W*3 == H*4:
	print "4:3"
else:
	print "16:9"

B - ドローン

"?"を除いた場合、どの座標に移動するかを求める。
後は"?"の数だけそこから原点に近づくまたは遠ざかる場合を考える。

S=raw_input()
T=input()

X=Y=P=0
for c in S:
	if c == 'L':
		X-=1
	if c == 'R':
		X+=1
	if c == 'U':
		Y-=1
	if c == 'D':
		Y+=1
	if c == '?':
		P+=1

D = abs(X) + abs(Y)

if T == 1:
	print D+P
else:
	if P > D:
		print (P-D)&1
	else:
		print D-P

C - オセロ

imos法の要領で、区間に対する反転回数の総和を求める。

import sys

N,Q=map(int,raw_input().strip().split(" "))
A=[0]*(N+1)

for i in range(Q):
	L,R=map(int,raw_input().strip().split(" "))
	A[L-1] += 1
	A[R] += 1

X = 0
for i in range(N):
	X += A[i]
	sys.stdout.write("%d" % (X&1))
print

D - トレジャーハント

各頂点iに対し、0番の頂点からi番に移動し、またi番から0番に帰る合計最短時間t[i]を求める。
あとは(T-t[i])*A[i]の最大値を求める。

以下のコードはPyPyでないとTLEする。

import Queue

N,M,T=map(int,raw_input().strip().split(" "))
A=map(int,raw_input().strip().split(" "))
E = [[],[]];
D = [[1<<30]*N,[1<<30]*N];

for i in range(N):
	E[0].append([])
	E[1].append([])

for i in range(M):
	a,b,c=map(int,raw_input().strip().split(" "))
	E[0][a-1].append((b-1,c))
	E[1][b-1].append((a-1,c))


Q = Queue.PriorityQueue()
D[0][0] = D[1][0] = 0
Q.put((0,0))
Q.put((0,1000000))

while not Q.empty():
	r = Q.get()
	cost = r[0]
	cur = r[1]%1000000
	ph = r[1]/1000000
	if D[ph][cur] != cost:
		continue
	
	for e in E[ph][cur]:
		if D[ph][e[0]] > cost + e[1]:
			D[ph][e[0]] = cost + e[1]	
			Q.put((D[ph][e[0]], ph*1000000+e[0]))

ma = 0
for i in range(N):
	ma = max(ma, (T - (D[0][i] + D[1][i])) * A[i])

print ma

まとめ

PythonのPriorityQueueは毎回使い方を忘れて検索する…。