競プロ弱者の解答

競プロ弱者の成長記録

ABC153:水色競プロerのムーブ備忘録(バグったら書き直しましょう。一から……いいえ、ゼロから！)

〇コンテスト名：ABC153

〇配点　 A:100 B:200 C:300 D:400 E:500 F:600

〇制限時間　 100分

　いつも通りのABC

〇コンテスト開始時のsyunsukeのレート　1367

〇今回の方針
　いつも通り。
　基本前から順番に解く。
　Cまではテストケースも程々に速度重視で。
　(Dが難しく、Cまでのペナで死にたくないので。)
　はまったら順位表をチェック。
　・今見てる問題を飛ばす？
　・何か簡単な解法がある？
　の判断材料に

コンテスト開始！
A:Hの体力をもつモンスターに一回でAの体力を削る。何回で体力を0以下にできるか？

pythonなら、mathのceilを使えば良いですね。

import math
H,A=map(int,input().split())
print(math.ceil(H/A))

　1:43 AC

B:Hの体力をもつモンスターに一回でAiの体力を削る必殺技を食らわせる。必殺技は一種につき一回。N種の必殺技でモンスターの体力を0以下にできるか？

Aをリストで受けて、リストの合計(sum(A))とHの大きさを比較すれば良いですね。

H,N=map(int,input().split())
A=list(map(int,input().split()))
if H-(sum(A))<=0:
    print("Yes")
else:
    print("No")

　3:57 AC

C:N体のモンスターがいる。体力はそれぞれHiで与えられる。1劇でモンスターを仕留められる必殺技をK回放てる。それ以外は1ずつ体力を削る。最低何回でモンスターを全滅させられるか？

自然に考えて、体力の大きいモンスターから順に必殺技を放ち、残りは1ずつ削る。
ではどうやって体力の大きいモンスターを探すか？
Hをリストで受けて、降順で並べ替える。
H.sort(reverse=True)を使えば、大きい方から順に並びます。
並べたら、最初からK体のモンスターの体力を０にして、あとはモンスターの体力の合計(sum(H))を出力すればOK
!!制約にKはNより小さいとは書いていません。
KがNより大きい場合、K体のモンスターの体力を０にしようとしたらバグりそうですね。
危ない

N,K=map(int,input().split())
H=list(map(int,input().split()))
H.sort(reverse=True)
for i in range(min(K,N)):
    H[i]=0
print(sum(H))

　6:32 AC

D:体力Hのモンスターがいる。H=1のときに攻撃すればモンスターは死ぬ。H>1なら体力H//2のモンスター2体に分裂する。何回の攻撃で倒せる(全滅させられる)か？
攻撃して、倒せなければ、モンスターの数は倍になって、それぞれのモンスターの体力は半分(小数点以下切り捨て)になる。
難しいことは考えずに、そのままコードに落としましょう。
答えはans
モンスターの数をNumとしてます。

H=int(input())
ans=0
Num=1
for i in range(100):
    if H==0:
        break
    else:
        ans+=Num
        H//=2
        Num*=2
print(ans)

ループの回数を100回にしていますが、
1回モンスターに攻撃するとモンスターの体力は2**1分の1に
10回攻撃すると2**10分の1に
ここで2**10>10**3は覚えておくと便利です。
制約からHは10**12以下
10回の攻撃で10**3分の1以下まで体力を削れるので
40回攻撃すれば、10**12分の1以下に削れます。
それを考えれば50回のループでも良いですね。
H=0となった時点で６行目のbreakでループを止めて
答えを出力

　11:35 AC

E:Hの体力を持つモンスターにN種類の魔法を食らわせる。各魔法はAiのダメージを与え、魔力をBi消費する。モンスターの体力を0にするために必要な最小の魔力の消費はいくらか？

どう見てもDPですね。
しかも、テストケースを見ると、魔力の消費の上限はかなり高い。でも制約を読むと体力の上限は10**4。
ここまでわかればあとはコードに落とすだけ。さっさと解きましょう。
・・
・・
・・
あれ？テストケース3が通りません。
途中で割り算を使ったから誤差が出ているのでしょうか？
割り算してmath.ceilで切り上げて・・
いや。それなら誤差はないでしょう。

一旦離脱してFを見てみましょう。
区間更新のライブラリがあれば解けそうですね。持ってませんけど。

こんな時は究極奥義。

全部消して
「ここからはじめましょう、一から……いいえ、ゼロから！」
あっさりテストケース通ります。

アルゴリズムが間違っていない自信があるのにテストケースに通らない場合は早めにやり直すべきですね。
今回はその判断が遅すぎました。

H,N=map(int,input().split())

L=[]
for i in range(N):
    a,b=map(int,input().split())
    L.append([a,b])
L.sort()
import math
X=math.ceil(H/L[i][0]*L[i][1])
dp=[10**20 for i in range(10**4+100)]
dp[0]=0
for i in range(N):
    for j in range(len(dp)):
        if j%L[i][0]==0:
            Y=j//L[i][0]
        else:
            Y=j//L[i][0]+1
        if j-L[i][0]>=0:
            dp[j]=min(dp[j],Y*L[i][1],dp[j-L[i][0]]+L[i][1])
        else:
            dp[j]=min(dp[j],Y*L[i][1])
print(dp[H])

汚いコードですが通りました。
10分で書けるコードを40分もバグがとれずに悩んでいてはコンテストで勝てません。
おまけにdpのリストの数を10**4にしてしまうミス(0から10**4まで欲しいので、10**4+1個もしくはN+1個のリストにしなければなりません)で1ペナ
　60::09 AC 1ペナ

F:N体のモンスターがいる。各モンスターの位置はXi体力はHi。攻撃は指定座標±Dに届く。何回で全滅させられるか？

区間の値を更新するライブラリが欲しいですね。
Google先生に期待しましょう。
それっぽいライブラリはすぐ見つかりますが、使い方がわかりません。
残り10分を切った頃
あれ？左端から攻撃して、攻撃の届く右の端と、その時与えるダメージの値をリストにしておいて、しゃくとり法を使えばライブラリいらない？
遅すぎました。
10分未満ではコードにできません。
Eで時間をロスしすぎなければあるいは・・

結局60:09で1ペナ5完

1587位でパフォ1137　レートは-21で1346になりました。
アルゴリズムに自信があるのにバグが取れないなら潔く書き直す。
次回以降の反省です！