AtCoder ARC #003 : Python練習編

続いてARC#003。問Cは事情により断念…。
http://arc003.contest.atcoder.jp/assignments

A - GPA計算

各教科ABCDFの成績が与えられたとき、平均点を返す。
間にEが無いことに気を付けて処理すればよい。

N=input()
S=raw_input()

t=0
for i in range(0,N):
	if S[i] != 'F':
		t += ord('E')-ord(S[i])

print float(t)/N

B - さかさま辞書

文字列を逆順にしたものを辞書順になるようにする問題。
実際逆にして辞書順ソートし、再度逆にすればよい。
文字列順を逆にするのにこんな方法があったのね…。

N=input()
S=[]
for i in range(0,N):
	S.append(raw_input()[::-1])

S.sort()
for i in range(0,N):
	print(S[i][::-1])

C - 暗闇帰り道

マス目ごとに明るさが与えられる。
始点から終点まで移動する際、移動ごとにマス目は暗くなっていく際、最大どの程度の明るさの道を通れば良いか答える。

C++で解いたときは、ある明るさ以上のマスだけ通って終点にたどり着けるかの関数を書き、あとは二分探索で求めていた。
ただ、今回Pythonで同じコードを書いたらTLEで通らず。手元でも20秒位かかるし。
よく見たらPythonでは誰も通していない…。
二分探索以外の解法も良くわからないし、TLEだけど今回はこれで良しとして次に行くことにした。

v99 = [0.99**i for i in range(500*501)]
Q=range(500*501)

def ok(P):
	Q[0]=sx*1000+sy
	vis=[[0 for a in range(W)] for b in range(H)]
	vis[sy][sx]=1
	dx=[(-1,0),(1,0),(0,1),(0,-1)]
	
	ql=1
	i=0
	while i<ql:
		pos=Q[i]
		x=pos/1000
		y=pos%1000
		for j in range(4):
			tx = x+dx[j][0]
			ty = y+dx[j][1]
			if tx < 0 or tx >= W or ty < 0 or ty >= H:
				continue
			
			if tx==gx and ty==gy:
				return 1
			if vis[ty][tx]>0:
				continue
			if M[ty][tx]*v99[vis[y][x]] >= P:
				vis[ty][tx]=vis[y][x]+1
				Q[ql]=tx*1000+ty
				ql += 1
		i+=1
	return 0

H,W=map(int,raw_input().split(" "))
M=[]
for i in range(H):
	M.append(list(raw_input()))

for y in range(H):
	for x in range(W):
		if M[y][x]=='s':
			sx=x
			sy=y
			M[y][x]=0.0
		elif M[y][x]=='g':
			gx=x
			gy=y
			M[y][x]=0.0
		elif M[y][x]=='#':
			M[y][x]=-1
		else:
			M[y][x]=float(M[y][x])

if ok(0)==0:
	print(-1)
	exit()

L=0.0
R=10.0
while R-L>0.0000000005:
	P = (L+R)/2.0
	#print(P)
	if ok(P):
		L=P
	else:
		R=P

print(L)

まとめ

GCJはPythonでも十分クリアできることを確認してたけど…。
この問題はスクリプト言語で解けるのかな…。