【ABC153】F - Silver Fox vs Monster

atcoder.jp

解法

モンスターは昇順に並び替えておく。
一番初めのモンスターに爆弾を当てるには最大で、X[0] + D * 2 までの座標で使用する必要がある。
なるべく別のモンスターに当てたいので、ギリギリ倒せる座標で使用した方がいい。
これを全てのモンスターで繰り返す、貪欲法をすれば答えを出せる。
ただし、後のモンスターは前のモンスターを倒すために使った爆弾のダメージを受けている可能性があるため、うまく処理する必要がある。

なぜ貪欲できると分かるのか

端のモンスターを倒す時には、そのモンスターにギリギリ当たる座標で爆発させるのが効率がよく、それ以外の座標で爆発させて端のモンスターを倒すメリットがないため。
端のモンスターを倒した後は、その隣にいるモンスターが次の端のモンスターに変化すると考えられる。
よって、同じことを繰り返すことによって答えが出せる。

実装

座標圧縮＋いもす法みたいな感じで実装する。

モンスターの座標を挿入したmultisetを準備しておく。
爆弾の爆発範囲外の座標もmultisetに挿入し、爆発の蓄積ダメージの計算に使う。 爆弾を爆発させた時に蓄積ダメージとして、ダメージを追加しておき、爆発の範囲端で減らしておく。
これで前のモンスターを倒すために使った爆弾の影響ダメージを計算できる。

void solve(long long N, long long D, long long A, std::vector<long long> X, std::vector<long long> H){
    multiset<pair<ll, ll>> st;
    REP (i, N) st.insert({X[i], H[i]});

    // zahyo: 現在の座標
    // damege: 蓄積ダメージ
    // ans: 答え
    ll zahyo = 0, damage = 0, ans = 0;
    auto iter = st.begin(); // イテレータ
    // 蓄積ダメージの計算に使用
    // first: 爆弾の爆発範囲端の座標, second: 爆発ダメージ
    map<ll, ll> mp;
    while (iter != st.end()) {
        // st.second()
        // 爆弾の爆発範囲端の場合: -1, それ以外の場合モンスターのヘルス
        if ((*iter).second != -1) {
            // 現在の対象モンスターが射程のギリギリになるように爆弾を使用
            zahyo = (*iter).first + D*2;
            // 爆弾の使用回数
            ll cnt = max(0LL, myceil((*iter).second-damage, A));

            ans += cnt;
            damage += A * cnt; // 蓄積ダメージを追加
            mp[zahyo+1] = A * cnt;
            // first: 爆発範囲の範囲外の座標
            st.insert({zahyo+1, -1});
        } else {
            // 蓄積ダメージを減らす
            damage -= mp[(*iter).first];
        }
        iter++;
    }

    cout << ans << endl;
}