30歳で競プロに目覚めた霊長類のブログ

ウホウホ (競プロの世界にやってきました。がんばります。)

Kyoto University Programming Contest 2017

結果

A,B の2完。タイム08:06。165位。
初の5時間越えのコンテストに参加するので、お菓子に飲み物と万全の体制で臨んだ。
なのに、C問題以降が難しすぎて、早々にダレてしまった。
これだけ時間があったら、せめてC問題は解きたかった...。
おのれ、京都大学ぅ〜。
後で解説きたら勉強させてもらおう...。


A Credits

A: Credits - Kyoto University Programming Contest 2017 | AtCoder

できるだけ少ない科目数で必要単位を取る場合の科目数を答える問題。

需要あるか分からないけど、コードペタペタしていく。

N,K = map(int,input().split())
src = list(map(int,input().split()))
src.sort(reverse=True)
ans = c = 0
for i in range(N):
    c += src[i]
    ans += 1
    if c >= K:
        print(ans)
        break
else:
    print(-1)

降順にソートして、貪欲に単位数を足していって、必要単位Kに達したらbreak。
全部足してもKに達しなかったら、-1。
Nは50までなので、計算量も余裕。


B Camphor Tree

B: Camphor Tree - Kyoto University Programming Contest 2017 | AtCoder

完全二分木の形のくすのきがあって、ある分岐Sからある分岐Tに登れるか。 登れる場合は距離を出力。登れない場合は-1。

N,S,T = map(int,input().split())
 
n = T
ans = 0
while(n >= S):
    if n == S:
        print(ans)
        break
    ans += 1
    n //= 2
else:
    print(-1)

完全二分木の性質を知っていれば楽勝でした。
2で割れば、1つ親のノードに行けるので、Sを2で割っていってTにたどり着けるかどうか。
木の高さN=25なので、計算量も余裕。