AtCoder ARC #010 : Python練習編

またC++とPythonの速度差が効く問題が出てきた…。
http://arc010.contest.atcoder.jp/assignments

C++でのコードはこちら。
http://kmjp.hatenablog.jp/entry/2012/12/21/0900
http://kmjp.hatenablog.jp/entry/2012/12/22/0900

A - 名刺交換

題意に沿って１日ずつ名刺を消費・追加していくだけ。

N,M,A,B=map(int,raw_input().split(" "))
for i in range(M):
	if N <= A:
		N += B
	N -= input()
	if N < 0:
		print(i+1)
		exit()

print("complete")

B - 超大型連休

土日に加え、祝日リストに沿って休日を追加していく。
狙った日付がすでに休日なら、翌日を狙う…というのを繰りかえす。

def day2int(M,D):
	MD=[31,29,31,30,31,30,31,31,30,31,30,31]
	d=D-1
	for i in range(0,M-1):
		d += MD[i]
	return d

B=[0] * 800
for i in range(100):
	if i*7 < 366:
		B[i*7]=1
	if i*7+6 < 366:
		B[i*7+6]=1

N=input()
for i in range(N):
	M,D=map(int,raw_input().split("/"))
	d = day2int(M,D)
	while B[d]==1:
		d+=1
	B[d]=1

ml=2
l=0
for i in range(366):
	l = (l + B[i]) * B[i]
	ml=max(l,ml)

print(ml)

C - 積み上げパズル

C++の時は50msで終わったDPのコードがPythonだと全然終わらない…。
M色で計N個のブロックに対し、O(M×2^M×N)のDPを書いたので、最大値であるM=10、N=5000に対しては約10000要素を5000回ループするだけで、C++なら余裕。

だが下記コード、「#continue」のコメントを外しても時間が足りない。
これって10000要素の配列に5000回初期値を入れるだけで終わっちゃう…。
copy関数使ってもほとんど変わらなかった。
下記コードだとTLEだけど、この問題はここで終わっておく。

N,M,Y,Z=map(int,raw_input().split(" "))
T={}
I={}
for i in range(M):
	c,v=raw_input().split(" ")
	T[c]=(i,int(v))

DP=[[[-99999999 for i in range(1<<M)] for j in range(M)] for k in range(2)]
DP[0][0][0]=0
B=list(raw_input())

for i in xrange(N):
	cur = i%2
	tar = cur^1
	for j in xrange(M<<M):
		DP[tar][j>>M][j%(1<<M)]=DP[cur][j>>M][j%(1<<M)]
	
	# continue
	ci=T[B[i]][0]
	for c in xrange(M):
		for mask in xrange(1<<M):
			if c==ci and (mask & (1<<ci)):
				DP[tar][ci][mask | (1<<ci)] = max(DP[tar][ci][mask | (1<<ci)], DP[cur][c][mask]+T[B[i]][1]+Y)
			else:
				DP[tar][ci][mask | (1<<ci)] = max(DP[tar][ci][mask | (1<<ci)], DP[cur][c][mask]+T[B[i]][1])

ma=0
for c in range(M):
	for mask in range((1<<M)-1):
		ma=max(ma,DP[N%2][c][mask])
	ma=max(ma,DP[N%2][c][(1<<M)-1]+Z)

print(ma)

まとめ

Pythonの配列処理やデータコピーの速度感覚にまだ慣れない…。