AtCoder ARC #005 : Python練習編

この位になると徐々に慣れてきました。
http://arc005.contest.atcoder.jp/assignments

A - 大好き高橋君 ( Love me do )

文章が与えられるので、そこに含まれる特定単語の数を答える。
最初は真面目に書いてみた。

N=input()
A=re.split("[ \.]",raw_input())
tot=0
for a in A:
	if a == "TAKAHASHIKUN":
		tot += 1
	if a == "Takahashikun":
		tot += 1
	if a == "takahashikun":
		tot += 1
 
print(tot)

次に１行で書いてみようと奮闘。
割と行ける。

print(len(re.findall(' (TAKAHASHIKUN|[Tt]akahashikun)(?=[ \.])',raw_input()+" "+raw_input())))

B - P-CASカードと高橋君 ( This story is a fiction )

9x9のマス目状に１ケタ数字が配置された表が与えられる。
また、始点と進行方向が与えられるので、その向きに従って４ケタの数値を作る。
題意通りにやるだけゲー。ただ、これでタプルの使い方を覚えられたね。

x,y,W=raw_input().split(" ")
x=int(x)-1
y=int(y)-1
S=[]
for i in range(0,9):
	S.append(raw_input())

ma={"R":(1,0),"L":(-1,0),"U":(0,-1),"D":(0,1),"RU":(1,-1),"RD":(1,1),"LU":(-1,-1),"LD":(-1,1)}
tx=ma[W][0]
ty=ma[W][1]


res = ''
for i in range(0,4):
	res += S[y][x]
	y += ty
	x += tx
	if x < 0:
		x = 1
		tx = -tx
	if x > 8:
		x = 7
		tx = -tx
	if y < 0:
		y = 1
		ty = -ty
	if y > 8:
		y = 7
		ty = -ty

print(res)

C - 器物損壊！高橋君 ( Search and destroy )

マス目状のマップに壁と平地がある。
始点から壁を最大２個まで壊して終点にたどり着けるかを答える。
単なるBFSをやるだけゲー。

…問題は、500x500マスのBFSで1.8秒かかっている。
先のARC#003は同じく500x500のBFSを35回程度行う必要があった。
こりゃやっぱりARC#003のCはPythonじゃ間に合わないよなぁ…。二分探索以外で一発で答えが出せる方法ならいいけどさ。

H,W=map(int,raw_input().split(" "))
S=[]
sx=sy=gx=gy=0
for y in range(H):
	S.append(list(raw_input()))
	for x in range(W):
		if S[y][x]=="s":
			sx=x
			sy=y
			S[y][x]='.'
		if S[y][x]=="g":
			gx=x
			gy=y
			S[y][x]='.'

D=[[999999 for i in range(501)] for j in range(501)]
D[sy][sx]=0

Q=[[(sy,sx)],[],[],[]]
i=0
j=0
while 1:
	while j<3 and i>=len(Q[j]):
		i=0
		j+=1
	if j>=3:
		break
	cy,cx=Q[j][i]
	for dx in [(1,0),(-1,0),(0,1),(0,-1)]:
		tx = cx+dx[0]
		ty = cy+dx[1]
		if tx < 0 or tx >= W or ty < 0 or ty >= H:
			continue
		cc = D[cy][cx]
		if S[ty][tx]=="#":
			cc += 1
		if cc < D[ty][tx] and cc < 3:
			D[ty][tx]=cc
			Q[cc].append((ty,tx))
	i += 1

if D[gy][gx] <= 2:
	print("YES")
else:
	print("NO")

まとめ

正規表現やらタプルやらぼちぼち主要な処理は出そろってきたかな。