最後から考えていく D - Katana Thrower abc085_d

Quiz

https://atcoder.jp/contests/abc085/tasks/abc085_d

Submit

https://atcoder.jp/contests/abc085/submissions/3878954

解き方

  • 最後の一発は投げるでも切るでもいい。1番ダメージの大きいものでとどめを刺す
  • 以下同様に、最後に投げた刀以外で最大ダメージの方法を探して選択する
  • 強い投げを使い果たし、投げ攻撃力<切り攻撃力になった時は、あとはその刀で切るだけ

f:id:peroon:20181227062545j:plain

  • 攻撃順番は左から行う。切切切投投投

追記:2020/10/19

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N,H;
    cin>>N>>H;

    priority_queue<PII> que; // (attack, attackable_num)

    rep(i,N){
      ll a,b;cin>>a>>b;
      que.push({a,inf});
      que.push({b,1});
    }

    ll cnt=0;
    while(!que.empty()){
      auto pa = que.top(); que.pop();
      ll attack = pa.first;
      if(pa.second==inf){
        // それで最後まで切り続ける
        ll num = (H+attack-1)/attack;
        p(cnt+num); return 0;
      }else{
        // 投げ切り
        H -= attack;
        cnt++;
        if(H<=0){
          p(cnt); return 0;
        }
      }
    }
    
    return 0;
}