AtCoder ARC #011 : Python練習編

そろそろ終盤戦。
http://arc011.contest.atcoder.jp/assignments

C++の時の記事はこちら。
http://kmjp.hatenablog.jp/entry/2013/01/19/0900
http://kmjp.hatenablog.jp/entry/2013/01/19/0930

A - 鉛筆リサイクルの新技術

残り鉛筆がm本以上あったら、全体の生産鉛筆数をn本増やし、残り鉛筆数を(m-n)本減らせばよい。
出てくる鉛筆数は多くないので、割り算などしなくても足し算引き算を繰り返しても間に合う。

m,n,N=map(int,raw_input().split(" "))
T=N
while N>=m:
	N-=(m-n)
	T+=n

print(T)

B - ルイス・キャロルの記憶術

文字を単純に数値に置換していけばいいが、空白になる単語の扱いがめんどい。
ここでは、空白は変換せず置いておき、最後に複数の空白を１つにまとめている。

m={"b":"1","c":"1","d":"2","w":"2","t":"3","j":"3","f":"4",
"q":"4","l":"5","v":"5","s":"6","x":"6","p":"7","m":"7",
"h":"8","k":"8","n":"9","g":"9","z":"0","r":"0"," ":" "}

N=input()
W=list(raw_input())
s=""
for w in W:
	s += m.get(w.lower(),"")
print(re.sub(" +"," ",s).strip())

C - ダブレット

文字列を１文字ずつ入れ替えて、ある文字列を別の文字列にしていく。
１文字だけ異なる文字列通しを辺でつないでグラフを作り、ダイクストラを実行すればよい。
各辺のコストは常に１なので、PriorityQueueも要らず、実質BFSで充分。

F,L=raw_input().strip().split(" ")
N=input()
W=[F,L]
for i in range(N):
	W.append(raw_input().strip())

W=list(set(W))
N=len(W)
tl=len(F)
fp=lp=0

for x in range(N):
	if W[x]==F:
		fp=x
	if W[x]==L:
		lp=x

if fp==lp:
	print(0)
	print(F)
	print(L)
	exit()
	
C=[999999 for i in range(N)]
P=[0 for i in range(N)]
C[fp]=0

Q=[fp]
qi=0

while qi < len(Q):
	cur=Q[qi]
	for i in range(N):
		if C[i]>C[cur]+1:
			v=0
			for z in range(tl):
				if W[cur][z]!=W[i][z]:
					v += 1
					if v>1:
						break
			if v==1:
				C[i]=C[cur]+1
				P[i]=cur
				Q.append(i)
	qi += 1

if C[lp]==999999:
	print(-1)
else:
	print(C[lp]-1)
	WL=[]
	i = lp
	while i != fp:
		WL.append(W[i])
		i=P[i]
	WL.reverse()
	print(F)
	for w in WL:
		print(w)
||

*まとめ

Cの問題、点が1000個のダイクストラで1.3秒か…。