AtCoder ABC 085 D - Katana Thrower (3Q, 緑色, 400 点)

昔ながらの典型考察 Greedy 問題。

• 問題へのリンク

問題概要

本の刀がある。

• 刀 を振ると、敵に だけダメージを与える。何度でも振ることができる
• 刀 を投げると、敵に だけダメージを与える。刀 を失うので、もう投げることも振ることもできなくなる

敵に だけダメージを与えるための最小回数を求めよ。

制約

• 
• 
• 

考えたこと

問題の条件では、刀 を投げてしまうと、もう投げることができなくなるだけではなく、振ることもできなくなってしまう。しかし、刀 を投げても、投げることはできなくなるが、振ることは依然としてできるものとしても最適解は変わらないことに着目しよう。

なぜならば、そのように緩和した問題で求めた最適解に対して、「投げる・振るという一連の動作において、投げるのを最後にする」というようにしても、敵に与えられるダメージは変わらないからだ。

よって、刀を失う心配をせずに、とにかく大きなダメージを与えられる攻撃から順番に実行していけばよい。計算量は となる。

コード

#include <bits/stdc++.h>
using namespace std;
using pll = pair<long long, int>;  // (damage, type)

int main() {
    long long N, H;
    cin >> N >> H;
    
    priority_queue<pll> que;
    for (int i = 0; i < N; ++i) {
        long long a, b;
        cin >> a >> b;
        que.push({a, 0});
        que.push({b, 1});
    }
 
    long long res = 0;
    while (H > 0) {
        auto [damage, t] = que.top();
        que.pop();
        if (t == 1) {
            // 投げる攻撃のとき (1 回きり)
            ++res;
            H -= damage;
        } else {
            // 振る攻撃のとき (敵のダメージが 0 になるまで振り続ける)
            res += (H + damage - 1) / damage;
            H = 0;
        }
    }
    cout << res << endl;
}