AtCoder ABC #038 : Python練習編

爆速で解けるはずのところを見落として1WAした上大幅タイムロス。
http://abc038.contest.atcoder.jp/assignments

A - お茶

最後の１文字を見ればよい。

S=raw_input().strip()

if S[-1]=="T":
	print "YES"
else:
	print "NO"

B - ディスプレイ

両ディスプレイ回転有無計４通りを総当たりしよう。

A1,B1=map(int,raw_input().strip().split(" "))
A2,B2=map(int,raw_input().strip().split(" "))

if A1==A2 or A1==B2 or B1==A2 or B1==B2:
	print "YES"
else:
	print "NO"

C - 単調増加

数列を先頭から見ていって、直前x個単調増加な部分列が続いているなら(x+1)を加算、ということを繰り返す。

N=input()
A=map(int,raw_input().strip().split(" "))
ret = L = 0

for i in range(N):
	if i>0 and A[i]<=A[i-1]:
		L = i
	ret += i-L+1

print ret

D - プレゼント

高さH[i]、幅W[i]の箱が計N個ある。
２つの箱は、片方がもう片方に比べ高さも幅も小さいなら、小さい方を中に入れて入れ個に出来る。
１つの箱に直接入れ子に出来るのは１つだけである。
これらの箱をできるだけ多く入れ個にしたい場合、最大何個入れ子に出来るか。

箱をH[i]昇順でソートし、W[i]からなる数列を考えるとLISを求めればいいことがわかる。
同じH[i]の箱は入れ子にしたくないので、同じH[i]の箱はW[i]が降順となるようにしておくとよい。

また、LISではなくRange Minimum Queryを解けるSegTreeを使っていく方法もある。
以下PyPyだと何とか通る。lower_bound代わりに自力で二分探索している。

N=input()
A = []

for i in range(N):
	A.append(map(int,raw_input().strip().split(" ")))
	A[-1][1] *= -1

A.sort()
P = [-x[1] for x in A]
LIS = [101010]*(N+1)
for i in P:
	L=0
	R=len(LIS)
	while L+1<R:
		t = (L+R)/2
		if LIS[t-1]<i:
			L=t
		else:
			R=t
	LIS[L]=i

for i in range(len(LIS)):
	if LIS[i]==101010:
		print i
		break

まとめ

Dは最初誤ったLISをした後SegTree解に移行したので1WAするわ大幅タイムロスするわ散々だった。
最初からちゃんと書けてれば7分で行けたなぁ…。