roiti46's blog

主に競プロ問題の解説を載せてます

Atcoder Beginner Contest 019 A,B,C,D

久しぶりに全完できたけどD問題で時間がかかりすぎた。木の基本的な知識が抜けてた。

問題はこちら

A: 高橋くんと年齢

3つの数字が与えられるので、その中の中央値(2番目に小さい値)を答えよ。

解法

やるだけ

print sorted(map(int,raw_input().split()))[1]

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

英小文字からなる文字列sが与えられる。aaabbbccdをa3b3c2d1のように圧縮する圧縮法をsに適用したときの結果を答えよ。

解法

空文字列のansを用意する。前から順番に見ていき、異なる文字が出てくるたびに圧縮結果をansに足していけばいい。ループから抜けた後の足し忘れに注意。

s = raw_input()
ans = ""
b = s[0]
cnt = 1
for si in s[1:]:
    if si!= b:
        ans += b+str(cnt)
        b = si
        cnt = 1
    else:
        cnt += 1
ans += b+str(cnt)
print ans

C: 高橋くんと魔法の箱

ある値xをいれるとある値を返す箱がある。基本的に異なるxでは異なる値を返すが、xと2xは同じ値を返す。数列を与えらえるので、その数列に含まれるxを箱に入れると一体いくつの種類の値が出てくるかを答えよ。

解法

ある素因数の2の倍数はどれも同じ値を返すので、与えられた数列中の数字を2で割り切れるだけ割り、最後に異なる数がいくつあるかを数えればいい。

N = int(raw_input())
a = map(int,raw_input().split())
for i in xrange(N):
    while a[i]%2 == 0: a[i] /= 2
print len(set(a))

D: 高橋くんと木の直径

頂点数N(≦ 50)の木が与えられる。それぞれの辺には重みがついており、各頂点間の距離はこの重みを足し合わせたものとする。今、ある2頂点間の距離を何度か尋ねることができる。そこから木の直径(最も距離の遠い2点間の距離)を推測して答えよ。

解法

部分点はすべての頂点間の組み合わせについて尋ね、その最大値を答えればいい。

満点解法は、まず1とそれ以外の頂点の距離を訪ねる。これで最大49回の質問となる。そのあと1からもっとも遠い頂点とそれ以外の頂点の距離を訪ねる。その最大値が答えとなり、100回以下で木の直径が求まる。木の直径の求め方として、まずある点からもっとも遠い点を探し、さらにそのもっとも遠い点から一番遠い点を探すというのが一般的なアルゴリズムのようだ。

import sys
N = int(raw_input())
mxdist = 0
for i in xrange(2,N+1):
    print "? %d %d"%(1,i)
    sys.stdout.flush()
    dist = int(raw_input())
    if dist > mxdist:
        mxdist = dist
        v = i
 
ans = mxdist
for i in xrange(2,N+1):
    if i == v: continue
    print "? %d %d"%(v,i)
    sys.stdout.flush()
    dist = int(raw_input())
    ans = max(ans,dist)
 
print "! %d"%ans
exit()