ABC085 D - Katana Thrower

atcoder.jp

最近は緑Diffを解いてみてる。 この問題、サクっと考察・実装できたものの、1WAが全然取れず苦戦した。

どこかというと if(H>0):がなかったわけだけど、 こうするとb（投げつける）で削りきったのに、 a（切り付ける）を処理してしまうので、NG。 ただし、bでちょうど削りきる場合は、残Hが0なので、これでもバグらない。

それもあって、テストケースにNG例が1つしか含まれていなくて、 大枠はあってそうなので、コーナーケース？と混乱したりした。 WAが少ないからと言って、コーナーケースばかり疑ってはいけないという教訓。。。

def resolve():
  N,H=map(int,input().split())

  ans=0

  a=[0]*N
  b=[0]*N
  
  for i in range(N):
    a[i],b[i]=map(int,input().split())

  a=sorted(a,reverse=True)
  b=sorted(b,reverse=True)

  for i in range(N):
    if(H<=0):
      break
    if(a[0]<b[i]):
      H-=b[i]
      ans+=1
    
  if(H>0):
    ans+=math.ceil(H/a[0])

  print(ans)