AtCoder Beginner Contest 119 参加記

はい。 https://atcoder.jp/contests/abc119
oox- 928(+9) でした。

A - Still TBD

Python3

print(["Heisei","TBD"][int(input().replace("/",""))>20190430])

問題文をさっぱりよく読んでいなかったのですが2019年の実在する日付だけならばmmだけ見れば大丈夫そうかな、と思いました。

B - Digital Gifts

Python3

n=int(input())
ans=0
for i in range(n):
    a,b=map(str,input().split())
    if b=="JPY": ans+=float(a)
    else: ans+=float(a)*380000
print(ans)

JPYとBTCを間違えず判定して加算し続ける。あと誤差とかに気をつける。でも多分そこまで意識して気にしなくてもなんとかなるのではないかと。

C - Synthetic Kadomatsu

Python3

def ns(X, n):
    if (int(X/n)):
        return ns(int(X/n), n)+str(X%n)
    return str(X%n)
 
n,a,b,c=map(int,input().split())
t=[a,b,c]
l=[]
ans=-1
for i in range(n):
    l.append(int(input()))
 
for i in range(4**n):
    tmp=ns(i,4)
    tmp="0"*(n-len(tmp))+tmp
    h=[0]*3
    p=0
    for j in range(n):
        if tmp[j]=="1":
            if h[0]!=0: p+=10
            h[0]+=l[j]
        elif tmp[j]=="2":
            if h[1]!=0: p+=10
            h[1]+=l[j]
        elif tmp[j]=="3":
            if h[2]!=0: p+=10
            h[2]+=l[j]
 
    if 0 in h:continue
    for k in range(3):
        p+=abs(h[k]-t[k])
    if ans==-1: ans=p
    else: ans=min(ans,p)
print(ans)

はい、概ね方針はあっていたのですがミスにより本番中にはAC出来ませんでした。方針としてはそれぞれ1本の棒に対して使わない、Aに使う、Bに使う、Cに使うの4通りが最大で8本の65536通りくらいを全部試します。
4進数を作って1桁目が1本目の棒、2桁目が2本目の棒...と割り当ててそれぞれの桁の数字が0なら使わない、1ならA、2ならB...という感じに。A,B,Cのそれぞれに2本目以上が割り当てられたらMP10発生の計算もする。割り当て終わったら指定されている長さとの差分のMP消費も計算する。あと割り当てがなかった場合にはcontinueでMP計算しないで(計算すると竹を選んでいない0から指定の長さに増やす操作になるからダメ)次のパターンを試しに行きました。
本番中は4進数の作り方が適当で桁数 < 棒の本数 の時に末尾に0を付け足していたのですが、それだと1本目の棒が必ず使うようになっていて全パターン試せていなくてWAでした。

D - Lazy Faith

Python3

import bisect
w=20000000001
a,b,q=map(int,input().split())
s=[int(input()) for i in range(a)]
t=[int(input()) for i in range(b)]
#bisect.bisect_left
 
for i in range(q):
    x=int(input())
    ans=w
    tmp=x
    ls=bisect.bisect_left(s,tmp)
    lt=bisect.bisect_left(t,tmp)
    if (s[ls-1]<=tmp and t[lt-1]<=tmp): ans=min(ans,tmp-min(s[ls-1],t[lt-1]))
    if (s[ls-1]<=tmp and lt<b and t[lt]>=tmp): ans=min(ans,(tmp-s[ls-1])+(t[lt]-s[ls-1]),(t[lt]-tmp)+(t[lt]-s[ls-1]))
    if (ls<a and s[ls]>=tmp and t[lt-1]<=tmp): ans=min(ans,(tmp-t[lt-1])+(s[ls]-t[lt-1]),(s[ls]-tmp)+(s[ls]-t[lt-1]))
    if (ls<a and lt<b and s[ls]>=tmp and t[lt]>=tmp): ans=min(ans,max(s[ls],t[lt])-tmp)
    print(ans)

コンテスト中にはできませんでした。割りと適当に調べてもなんとかTLEにならずセーフみたいです。寺・神社を西だけに探しに行く、どちらかを西(東)で探してから折り返して東(西)に探しに行く、東だけに探しに行くのを適当に調べます。折り返す前にどちらを先に行ってるかで合計距離変わるので両方計算する。折り返す前に完了してるパターンがありえますけども、それは西(東)だけ探すパターンになるので問題ないです。もう少しシンプルに書けると思うんですけど夜遅い時間なのでここまで。