AtCoder Beginner Contest 153
はい。
https://atcoder.jp/contests/abc153
oooox- 899(-6) D問題まで。E問題は終了10分後くらいにACは痛いです。
A - Serval vs Monster
PyPy3
h,a=map(int,input().split()) print((h+a-1)//a)
繰り上げになるように割り算。
B - Common Raccoon vs Monster
PyPy3
h,n=map(int,input().split()) a=[int(i) for i in input().split()] print("Yes" if h<=sum(a) else "No")
必殺技Aの合計と体力Hを比較します。
C - Fennec vs Monster
PyPy3
n,k=map(int,input().split()) h=[int(i) for i in input().split()] ans=chk=0 h.sort() for a,i in enumerate(h[::-1]): if a>=k: ans+=i print(ans)
K回の必殺技は体力の多いモンスターを優先に。以降は1ずつ攻撃で合計を求めます。
D - Caracal vs Monster
PyPy3
h=int(input()) x=h ans,cnt=0,0 while x>0: cnt+=1 x//=2 for i in range(cnt): ans+=pow(2,i) print(ans)
Hが2で割れる回数を調べて20からforループで累積和でしょうか、多分。
E - Crested Ibis vs Monster
PyPy3
h,n=map(int,input().split()) l=[] ans=0 for i in range(n): a,b=map(int,input().split()) l.append((a,b)) d=[0]*10005 for i in range(h): for j in l: a,b=j[0],j[1] x=d[i]+b y=min(10004,i+a) if i==0 or (d[i]!=0 and d[y]==0): if d[y]==0: d[y]=x else: d[y]=min(d[y],x) elif d[i]!=0 and d[y]!=0: d[y]=min(d[y],x) for i in range(h,10005): if ans==0: ans=d[i] elif d[i]!=0: ans=min(ans,d[i]) print(ans)
2次元配列でも出来るらしいですけど分かりません。1次元配列で計算する方法しか分かりません。dp[ダメージ]=コスト インデックスを与えているダメージにして、値をコストにする方法しか分かりません。与えているダメージ0からスタートして全攻撃試します。ダメージ1以降は既にコストが発生している時だけ試します。コストが発生していない時は攻撃パターンの組合せで発生があり得ないダメージです。ナップザック問題らしいです。