ABC085 D - Katana Thrower 精進と振り返り

問題

• ABC085 D - Katana Thrower
• Editorial

自分のたどり着いたアイディア

• i番目の刀を使うと決めたならば、最終的にはその刀は投げるべき
• $a_i$の最大値$\max(a)$よりも$b$が小さい刀は使う価値がない
• 投げるだけ投げてから、$\max(a)$の刀を先に何回振るかと考えればよい

Editorialの解説における表現

• すでに投げてしまった刀も振ることができるというルールに変更しても問題の答えは変わりません。
• However, the answer does not change if we change the rule to allow wielding a katana that you have already thrown.

解法を忘れたつもりで、もう一度思いつくためにどうするかを考える

Hを出すための最小回数と言われた

• 攻撃回数を決めて最大ダメージを出すには？ => Hを出すための最小回数xから、xで出せる最大値Hとの間の相互変換が可能？
• ある攻撃回数でHを出せるかを判定するには？→あまり実りはなかった。疑問: 最小最大問題を判定問題に置き換えることで実りがあるのはどのような場合だろうか？
• 判定できればバイナリサーチが可能

一度投げた刀はもう使えないという条件

• 一見ややこしい
• 本当にややこしいのか？単純な条件に同値変形できるのではないか？
• この**ややこしい条件を無視したらどうなるのか？**→やってみる→答えは変わらない、条件を無視したときに振る回数が決まれば先に振っておくことにすればいいだけだから。

実験

• N=1で実験→「i番目の刀を使うと決めたならば、最終的にはその刀は投げるべき」に気づく
• N=2,3で実験→これをしていたときはあまり気付きがなかった

教訓？

• 手を動かそう
• ルールを破ってみよう

書いたコード

N,H = map(int,input().split())
a=[]
b=[]
for i in range(N):
    x,y=map(int,input().split())
    a.append(x)
    b.append(y)

maxA = max(a)
b.sort()
b.reverse()

ans=0
index=0
for throwedKatana in b:
    if throwedKatana < maxA:
        break
    H -= throwedKatana
    ans += 1
    if H <= 0:
        break
if H > 0:
    ans += H//maxA
    if H%maxA != 0:
        ans += 1
print(ans)