AtCoder ABC #030 : Python練習編

しょうもない1WAしてしまったのが残念。
http://abc030.contest.atcoder.jp/assignments

A - 勝率計算

A試合中B回勝った人とC試合中D回勝った人はどちらの勝率が高いか。

B/AとD/Cを比べても良いが、小数は誤差が怖いのでB*CとD*Aを比較すると安全。

A,B,C,D=map(int,raw_input().strip().split(" "))

if B*C<A*D:
	print "AOKI"
elif B*C>A*D:
	print "TAKAHASHI"
else:
	print "DRAW"

B - 時計盤

H時M分を指す時計盤の短針と長針の角度差を求めよ。

長針は1分あたり6度、短針は1分あたり0.5度進むことを用いて両者の角度を求める。

H,M=map(int,raw_input().strip().split(" "))
H %= 12

short = M*6
long = (H*60+M)/2.0
dif = abs(short-long)

print min(dif,360-dif)

C - 飛行機乗り

空港AからBに行く飛行機N本及びBからAに行く飛行機M本の出発時刻が与えられる。
AからBに行く各飛行機の移動時間はX、BからAに行く各飛行機の移動時間はYである。
初期状態で時刻0に空港Aにいるとき、最大何往復できるか。

今いる時刻に最も近い出発時刻の飛行機を貪欲に探せばよい。
lower_bound等で二分探索してもよいし、尺取法の要領でもよい。

import bisect

N,M=map(int,raw_input().strip().split(" "))
X,Y=map(int,raw_input().strip().split(" "))
A=map(int,raw_input().strip().split(" "))
B=map(int,raw_input().strip().split(" "))

t = 0
lp = 0

while 1:
	
	id = bisect.bisect_left(A, t)
	if id>=N:
		break
	t = A[id]+X
	
	id = bisect.bisect_left(B, t)
	if id>=M:
		break
	t = B[id]+Y
	lp += 1

print lp

D - へんてこ辞書

N要素の数列B[i]が与えられる。
初期値をAに対しA=B[A]として状態を更新する処理をK回行った後の値を求めよ。

最大でもN回シミュレートするとどこかでループするので、ループを検出次第残りのKに対しそのループ間隔で剰余を取ればよい。
C++でも解けなくはないが、面倒なのでPython+多倍長で解いてしまった。

N,A=map(int,raw_input().strip().split(" "))
K=input()
B=map(int,raw_input().strip().split(" "))

P=[-1]*100010

pat=0
C=A
P[C]=0

while 1:
	if K<=0:
		break
	K-=1
	C=B[C-1]
	pat += 1
	if P[C]>=0:
		lp=pat-P[C]
		K %= lp
	P[C]=pat

print C

まとめ

Dは教育的な意味では多倍長使わずに解くべきだった…？