kmjp's blog

競技プログラミング参加記です

AtCoder ARC #004 : Python練習編

#003ではPythonの遅さにげんなりしてしまったけど、気を取り直して。
http://arc004.contest.atcoder.jp/assignments

A - 2点間距離の最大値 ( The longest distance )

100個の点の座標が与えられるので、距離の最大値を求める。
点の数が少ないしやるだけゲー。

N=input()

for i in range(0,N):
	XY=raw_input().split(" ")
	S.append((int(XY[0]),int(XY[1])))

ma=0.0
for i in range(0,N):
	for j in range(0,N):
		ma=max(ma, ((S[i][0]-S[j][0])**2+(S[i][1]-S[j][1])**2)**0.5)

print(ma)

B - 2点間距離の最大と最小 ( Maximum and Minimum )

N個の点がN-1本の線で1列に連結されている。始点と終点の距離の最小・最大値を求める。
最大値は全部の線の長さの和。最小値は、全体の半分以上の長さの辺がなければ0、あれば最長辺からそれ以外の辺の長さを引けばよい。

N=input()
tot=0
ma=0

for i in range(0,N):
	a=input()
	tot += a
	ma = max(ma, a)

print(tot)

if ma > tot - ma :
	print(ma-(tot-ma))
else:
	print(0)

C - 平均値太郎の憂鬱 ( The melancholy of Taro Heikinchi )

1~Nのうち平均値を取る際、ある1つの値Mを足し忘れて計算をしたらX/Yになった。
XとYが与えられたときにNとMの候補を列挙する。
Nの候補は2*X/Yの周辺になるので、後は地道に方程式を解いていくだけ。

X,Y=map(int,raw_input().split("/"))

R=[]
for N in range(2*X/Y-5,2*X/Y+5):
	if N<=0:
		continue
	U=N*((N+1)*Y-2*X)
	D=2*Y
	if U%D>0:
		continue
	M=U/D
	if 1<=M<=N:
		R.append((N,M))

if len(R)==0:
	print("Impossible")
else:
	for i in R:
		print "%d %d"%(i[0],i[1])

まとめ

A <= X <= Bみたいな書き方ができるのはいいね。