d_tail's blog

備忘や記録

【参加記録】AtCoder Beginner Contest 119

はじめに

AtCoder Beginner Contest 119に参加した記録です.

atcoder.jp

A - Still TBD

入力を'/'で分けて項目ごとに比較. なぜか7分も溶かしてしまいました.

S = input()
S = S.split('/')

if int(S[0]) <= 2019 and int(S[1]) <= 4 and int(S[2]) <= 30:
    print('Heisei')
else:
    print('TBD')

わざわざ分けなくても単純に辞書順で比較できるそうです.以下解説コード.

S = input()
print('Heisei' if S <= '2019/04/30' else 'TBD')

B - Digital Gifts

入力をループで回して加算していく.単位がBTCだったら380000.0を乗算したものを加算.

N = int(input())
in_num = []
for i in range(N):
    in_num.append(list(map(str,input().split())))

res = 0

for x,u in in_num:
    if u == 'JPY':
        res+=float(x)
    else:
        res+= float(x)*380000.0

print(res)

C - Synthetic Kadomatsu

時間内に解けず.
解説によると,N本の竹に対して,ABCの竹に使うかどれにも使わないかの4通りの使い方を全探索すれば良いらしいです.
解説ではDFSを使用していました.
以下解説コードに自分用にコメントを追加したもの.

N, A, B, C = map(int, input().split())
l = [int(input()) for i in range(N)]
INF = 10 ** 9

def dfs(cur, a, b, c):
    '''
    深さがNだったら使用MPを評価
    N本の竹を使うときに必要な合成回数はN-1のため,最後に-1*10*3(?)
    1本も竹を使用していなかったら棄却→MPを無限に使うこととしている
    '''
    if cur == N:
        return abs(a - A) + abs(b - B) + abs(c - C) - 30 if min(a, b, c) > 0 else INF

    '''
    cur番目の竹に対して
        ret0:ABCどれにも使わない
        ret1:Aに使う(合成:MP+10)
        ret2:Bに使う(合成:MP+10)
        ret3:Cに使う(合成:MP+10)
    '''
    ret0 = dfs(cur + 1, a, b, c)
    ret1 = dfs(cur + 1, a + l[cur], b, c) + 10
    ret2 = dfs(cur + 1, a, b + l[cur], c) + 10
    ret3 = dfs(cur + 1, a, b, c + l[cur]) + 10
    return min(ret0, ret1, ret2, ret3)
print(dfs(0, 0, 0, 0))

なんとなく作成してみた図(https://www.draw.io/):

f:id:d_tail:20190225115748p:plain

参考記事:
blog.192.works

D - Lazy Faith

問題を読むまでに至らず…

コメント

最近はSolversの多い順に300~400点の過去問を解いていましたが,本格的にアルゴリズムの勉強に立ち向かわないとダメそうです.