AtCoder ABC #037 : Python練習編

前回に引き続き今回も「どうやったらこれ以上速くなるの」という感じ。
http://abc037.contest.atcoder.jp/assignments

A - 饅頭

安い方を沢山買えばよい。

A,B,C=map(int,raw_input().strip().split(" "))
print C/min(A,B)

B - 編集

愚直に指示通りのコードを書いても間に合う。

N,Q=map(int,raw_input().strip().split(" "))

A=[0]*N

for i in range(Q):
	L,R,T=map(int,raw_input().strip().split(" "))
	for x in range(L-1,R):
		A[x] = T

for a in A:
	print a

C - 総和

累積和を取っておけば、１回分の連続部分列の総和を求める処理はO(1)で出来る。
各要素何回分カウントされるか数えても良さそうね。

N,K=map(int,raw_input().strip().split(" "))
A=map(int,raw_input().strip().split(" "))
S=[0] * (N+1)
for i in range(N):
	S[i+1] = S[i] + A[i]

ret = 0
for i in range(K-1,N):
	ret += S[i+1]-S[i+1-K]

print ret

D - 経路

要素の小さい順にDPで隣接するより大きなセルに移動経路の数を足しこんで行こう。
なお、以下のコードはPyPyでもTLEした。

H,W=map(int,raw_input().strip().split(" "))
S = []
dp = []
mo = 1000000007
cand = []

for y in range(H):
	S.append(map(int,raw_input().strip().split(" ")))
	dp.append([1]*W)
	for x in range(W):
		cand.append((S[y][x],(y,x)))

ret = 0
for e in sorted(cand):
	cy,cx = e[1]
	ret += dp[cy][cx]
	for d in ((-1,0),(0,-1),(1,0),(0,1)):
		ty = cy+d[0]
		tx = cx+d[1]
		if tx >= 0 and ty>=0 and tx<W and ty<H and S[ty][tx] > S[cy][cx]:
			dp[ty][tx] += dp[cy][cx] % mo

print ret % mo

まとめ

Dみたいのいい加減ライブラリ化しようかな…。