AtCoder ABC #033 : Python練習編

しょうもないミスさえなければぶっちぎりタイムで1位取れたのに…。
http://abc033.contest.atcoder.jp/assignments

前回記載通り、A,B,Cの解説は簡単に。

A - 暗証番号

ソートして先頭と末尾が一緒か見る。

S=list(raw_input())
S.sort()
if S[0]==S[-1]:
	print "SAME"
else:
	print "DIFFERENT"

B - 町の合併

指示通り数える。
本番過半数なのにちょうど半数でも良いと勘違いしてWAした…。

N=input()
S=[]
P=[]
sum=0

for i in range(N):
	x,y=raw_input().strip().split(" ")
	S.append(x)
	P.append(int(y))
	sum += P[-1]

A="atcoder"
for i in range(N):
	if P[i]*2 > sum:
		A=S[i]

print A

C - 数式の書き換え

"+"で区切られた各項について、最低1個ゼロがあるように0を加える。
C++だと入力を"+"でsplitしてもよいが、Pythonだと明に"+"でsplitするとTLEする。

S=raw_input()

ret = 0
zero = 0
for c in S:
	if c=='0':
		zero=1
	elif c=='+':
		ret += 1-zero
		zero=0

print ret + (1-zero)

D - 三角形の分類

２次元座標でN個の頂点が与えられる。
これらのうち３点を結んでできる三角形のうち、鋭角・直角・鈍角三角形の数を求めよ。

鋭角は三角形に複数あるが、直角・鈍角は１個しかないので、直角・鈍角三角形を数え上げよう。
全三角形から直角・鈍角三角形の数を引けば鋭角三角形の数がわかる。

１点を総当たりし、残りの頂点を偏角ソートする。
ソート済みの各頂点に対し、尺取法の要領で偏角が90度以上左側にある最初の点と、180以上左側にある最初の点を求めれば、その間にある点を３点目に取れば直角三角形または鈍角三角形になる。

なお以下のコードはTLEする。C++だと1.2s程度でACが取れる。

import math

N=input()
X=[]
Y=[]

for i in range(N):
	x,y=map(int,raw_input().strip().split(" "))
	X.append(x)
	Y.append(y)

eps = 1e-9
A=B=C=0
for i in range(N):
	P = []
	for j in range(N):
		if i!=j:
			P.append(math.atan2(Y[j]-Y[i],X[j]-X[i]))
	
	P.sort()
	for j in range(N-1):
		P.append(P[j]+2*math.pi)
	
	y=z=0
	for x in range(N-1):
		while P[y]-P[x] < math.pi/2-eps:
			y+=1
		while P[z]-P[x] < math.pi+eps:
			z+=1
		if math.fabs(P[y]-P[x]-math.pi/2)<2*eps:
			B += 1
			y += 1
		C += z-y

A=N*(N-1)*(N-2)/6-B-C

print A,B,C

まとめ

Dはepsを小さく取りすぎる→厳密に90度判定しようと思って内積外積判定を書こうとする→面倒なのでやめてlong doubleにしてもっと小さいepsにするで通した。
でもよくよくみたらlong doubleでなくても最初にepsをもっと小さく取っておけばそれで十分だった。

…Bもろくでもないミスしてるし、両ミスが無ければ15分切れたのに。
最近しょうもないミスが多い。今晩のSRMは何もないと良いのだが。