しょうもないミスさえなければぶっちぎりタイムで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 - 三角形の分類
2次元座標でN個の頂点が与えられる。
これらのうち3点を結んでできる三角形のうち、鋭角・直角・鈍角三角形の数を求めよ。
鋭角は三角形に複数あるが、直角・鈍角は1個しかないので、直角・鈍角三角形を数え上げよう。
全三角形から直角・鈍角三角形の数を引けば鋭角三角形の数がわかる。
1点を総当たりし、残りの頂点を偏角ソートする。
ソート済みの各頂点に対し、尺取法の要領で偏角が90度以上左側にある最初の点と、180以上左側にある最初の点を求めれば、その間にある点を3点目に取れば直角三角形または鈍角三角形になる。
なお以下のコードは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は何もないと良いのだが。