kmjp's blog

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

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)

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

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

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

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

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 )

マス目状のマップに壁と平地がある。
始点から壁を最大2個まで壊して終点にたどり着けるかを答える。
単なる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")

まとめ

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

広告を非表示にする