AtCoder Beginner Contest 087/AtCoder Regular Contest 090
はい。
https://atcoder.jp/contests/abc087
A - Buying Sweets
Python3
x=int(input()) a=int(input()) b=int(input()) print((x-a)%b)
A円のケーキが必ず1個になってて0個があり得るとかないので慎重に書けば大丈夫だと思う。。
B - Coins
Python3
a=int(input()) b=int(input()) c=int(input()) x=int(input()) ans=chk=0 for i in range(a+1): for j in range(b+1): tmp=i*500+j*100 if x-tmp>=0 and (x-tmp)//50<=c: ans+=1
500円と100円の使い方を総当たりして、あとは50円で調整できるかを確認した。。。
C - Candies
Python3
n=int(input()) a=[int(i) for i in input().split()] b=[int(i) for i in input().split()] ans=chk=sum(a)+b[-1] for i in range(-1,-n,-1): chk=chk-a[i]+b[i-1] ans=max(ans,chk) print(ans)
最後にだけ曲がる場合を基準にして1つずつ手前にずらしながら最高値を確認した。
D - People on a Line
PyPy3
def sol(): n,m=map(int,input().split()) t,w={},{} p,q=set(),set() for i in range(m): l,r,d=[int(i) for i in input().split()] if l in w: w[l].add((r,d)) else: w[l]={(r,d)} p.add(l) q.add(r) s=p-q chk=set() if len(s)==0: print(["No","Yes"][m==0]) exit() for i in s: chk.add((i,0)) while len(chk): x=chk.pop() if x[0] in w: for j in w[x[0]]: if (i,j[0]) in t and t[(i,j[0])]!=t[(i,x[0])]+j[1]: print("No") exit() elif (i,j[0]) not in t: #t[(i,j[0])]=t[(i,x[0])]+j[1] t[(i,j[0])]=x[1]+j[1] chk.add((j[0],x[1]+j[1])) print("Yes") if __name__=="__main__": sol()
かなり苦戦しました。もっと軽く単純な経路の管理の仕方があると思います。2次元配列を 10万×10万 のサイズで用意しようとするとあっという間にMLEになるようでした。事前に準備してある場合ですと重み付きUnionFindをぺたっとコピペでACしたり出来るようです。
そうでない場合は経路を探索して同じ経路で違うコストを発見したらNoにして、ソレが見つからずに経路探索終了したらYesという感じでしょうか。これをもっとスムーズに書けないとなのですけど数日掛けて沢山サブミットデバッグしてからなんとかAC出しました。