AtCoder ABC #019 : Python練習編

ABC#019に参加。
A～Cまで順調なもののDで無駄に3WAして大幅に順位を落とす。
http://abc019.contest.atcoder.jp/assignments

A - 高橋くんと年齢

3つの整数の中央値を求めよ。

ソートして真ん中を出力。FAに4秒及ばず。

A=map(int,raw_input().strip().split())
A.sort()
print A[1]

B - 高橋くんと文字列圧縮

文字列が与えられるので、ランレングス圧縮した文字列を返せ。

直前の(文字,繰り返し数)の対を更新していけば良い。
これPythonの方が出力に余計な文字を入れないようにするのが面倒かも。
これはFA取れた。

S=raw_input().strip()
V=[]

for s in S:
	if len(V)==0 or V[-1][0]!=s:
		V.append([s,1])
	else:
		V[-1][1] += 1

s=""
for v in V:
	s += "%s%d" % (v[0],v[1])
print s

C - 高橋くんと魔法の箱

ある箱に整数xを入れると2xを入れたときと同じ値が返る。
N個の整数A[i]を入れたとき、返る値は何通りか。

A[i]を奇数になるまで2で割り、その結果の値の種類をsetで数える。

from sets import Set

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

S = Set()
for a in A:
	while a % 2 == 0:
		a /= 2
	S.add(a)

print len(S)

D - 高橋くんと木の直径

N頂点の木を成すグラフが与えられる。
各辺には長さが割り当てられている。
クエリとして2頂点の番号を与えると、2頂点間の最短距離が返る。
この木の直径を求めよ。

木の直径はARC#022で登場しており、適当な頂点からの最遠点を求めたうえ、さらにその最遠点からの最遠点を求めるとその2頂点の距離が直径となる。
よって2(N-1)回のクエリで直径を求めることができる。

import sys

N=input()
ma = id = 0
for i in range(1,N):
	print "? {0} {1}".format(1, i+1)
	sys.stdout.flush()
	dist = int(raw_input())
	if dist > ma:
		id = i
		ma = dist

ma = 0
for i in range(0,N):
	print "? {0} {1}".format(id+1, i+1)
	sys.stdout.flush()
	dist = int(raw_input())
	if dist > ma:
		ma = dist

print "! %d" % (ma)

まとめ

せっかく10分ぐらいで解いたのに、3WAはもったいなかった。