AtCoder ABC #005 : Python練習編

ABC#005に参加。
なんとか順調に解いて2位を取ったけど、1位とはだいぶ時間に開きがある…。
http://abc005.contest.atcoder.jp/assignments

A - おいしいたこ焼きの作り方

X,Yが与えられるのでY/Xの整数部を答えよ。
割るだけ。

import sys
X,Y=map(int,raw_input().strip().split(" "))
print Y/X

B - おいしいたこ焼きの食べ方

T[i]の最小値を求めよ。最小値を更新していくだけ。

import sys

N=input()
ma=1000
for i in range(0,N):
	x=input()
	ma=min(ma,x)

print ma

C - おいしいたこ焼きの売り方

たこ焼き屋でN個のたこ焼きが出来るタイミングA[i]と、来客のタイミングB[i]が与えられる。
来客は来店時から時間T以内に作られたたこ焼きがあれば、それを買っていく。
来客全員にたこ焼きを売ることはできるか？

(B[i]-T)～(B[i])の間に作られたたこ焼きのうち、古いものを買って行ってもらえばよい。

T=input()
N=input()
A=[0]*101
AA=map(int,raw_input().strip().split(" "))
M=input()
BB=map(int,raw_input().strip().split(" "))

for i in AA:
	A[i] += 1

for i in BB:
	ng=1
	for j in range(max(0,i-T),i+1):
		if A[j]>0:
			A[j]-=1
			ng=0
			break;
	
	if ng>0:
		print "no"
		sys.exit(0)

print "yes"

D - おいしいたこ焼きの焼き方

NxNの行列D[i][j]が与えられる。
ここでQ種類のクエリが与えられ、それぞれの値はP[i]である。
各クエリに対し、行列DでP[i]以下の面積分の長方形を選ぶことができるとき、D[i][j]の総和を最大化せよ。

各長方形を全部列挙し、面積に対応したD[i][j]の総和の最大値を更新していけばよい。
長方形の選び方がO(N^4)あり、愚直に計算するとD[i][j]の総和を求めるとO(N^2)かかる。
合わせてO(N^6)はPythonだとTLEするので、事前に長方形内のD[i][j]の和をO(1)で求められるようD[i][j]の累積和を求めておくとよい。

本番はC++だったので、累積和が1次元分だけ取ってO(N^5)で通した。

import sys

N=input()
D=[]
for y in range(0,N):
	D.append(map(int,raw_input().strip().split(" ")))

S=[[0 for j in range(N+1)] for i in range(N+1)]

for y in range(0,N):
	for x in range(0,N):
		S[y+1][x+1]=S[y+1][x]+D[y][x]

for y in range(0,N):
	for x in range(0,N):
		S[y+1][x+1]+=S[y][x+1]

M=[0] * 2501
for y in range(0,N):
	for x in range(0,N):
		for h in range(0,N-y):
			for w in range(0,N-x):
				v = S[y+h+1][x+w+1]+S[y][x]-S[y+h+1][x]-S[y][x+w+1]
				M[(h+1)*(w+1)]=max(M[(h+1)*(w+1)],v)

for i in range(1,2500):
	M[i]=max(M[i],M[i-1])

Q=input()
for i in range(0,Q):
	x=input()
	print M[x]

まとめ

あと3分早くするのは厳しいなぁ。
最初Dは累積和使わずO(N^6)で書いてたけど、これで通ったとしても3分は短縮できない。