[AtCoder] ABC 153 F – Silver Fox vs Monster

2020年1月28日2020年12月15日

問題

方針

モンスターの順序は問題に影響を与えないので、モンスターの座標について昇順に並び替えて考えます。

最適な攻撃方法

最適な攻撃方法は、モンスターの先頭から爆弾を使っていくやり方です。爆弾の位置は、爆弾の範囲の最も左を今注目しているモンスターの座標に与えます。したがって、\( 1 \) 回目の爆弾の範囲は、\(  [X_1, X_1 + 2D] \) となります。この地点に落とす爆弾の回数 \( t_1 \) は、

\[ t_1 = \left \lfloor \dfrac{H_1 + A – 1}{A} \right \rfloor\]

となります。このとき、この範囲のモンスターには \( t_1D \) のダメージが与えられます。同様にして、モンスター \( 2 \) の体力が残っている場合も上記のように爆弾を使います。

爆弾の範囲に含まれるモンスター

上記の方法で爆弾を落とした時に含まれるモンスターを考えます。例えば、爆弾をモンスター \( i \) が範囲の最も左側にいるとします。このとき、\( X_j \leq X_i + 2D \) を満たす最大の \( j \) までのモンスターが爆弾の範囲に含まれます。これは、二分探索によって求めることができます。

ダメージの管理

ダメージの管理は遅延評価セグメント木を使って対応します。評価遅延セグメント木が詳しいです。遅延セグメント木は、

の問題が解ければこの問題も解くことができます。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

class SegmentTree {
private:
    int n;
    vector<ll> node, lazy;
    ll INF = (1ll << 31) - 1;
public:
    SegmentTree(int N) {
        n = 1;
        while (n < N) n *= 2;
        node.resize(2 * n - 1, 0);
        lazy.resize(2 * n - 1, 0);
    }

    void update(int i, int l, int r) {
        if (lazy[i] == 0) return;
        node[i] += lazy[i];
        if (r - l > 1) {
            lazy[2 * i + 1] += lazy[i] / 2;
            lazy[2 * i + 2] += lazy[i] / 2;
        }
        lazy[i] = 0;
    }

    void add(int a, int b, ll x, int k = 0, int l = 0, int r = -1) {
        if (r < 0) r = n;
        update(k, l, r);
        if (b <= l || r <= a) return;
        
        if (a <= l && r <= b) {
            lazy[k] += (r - l) * x;
            update(k, l, r);
        } else {
            add(a, b, x, 2 * k + 1, l, (l + r) / 2);
            add(a, b, x, 2 * k + 2, (l + r) / 2, r);
            node[k] = node[2 * k + 1] + node[2 * k + 2];
        }
    }

    ll query(int a, int b, int k = 0, int l = 0, int r = -1) {
        if (r < 0) r = n;
        update(k, l, r);
        if (b <= l || r <= a) return 0;        
        if (a <= l && r <= b) return node[k];

        ll sum_l = query(a, b, 2 * k + 1, l, (l + r) / 2);
        ll sum_r = query(a, b, 2 * k + 2, (l + r) / 2, r);
        return sum_l + sum_r;
    }

};


int main() {
    int N;
    ll D, A;
    cin >> N >> D >> A;
    vector<pair<ll, ll>> v(N);
    for (int i = 0; i < N; i++) {
        ll X, H;
        cin >> X >> H;
        v[i] = make_pair(X, H);
    }
    sort(v.begin(), v.end());
    SegmentTree st(N);
    int size = 1;
    while (N < size) size *= 2;
    ll f[N + 1][2]{};
    ll ans = 0;
    for (int i = 0; i < N; i++) {
        int l = i - 1;
        int r = N;
        while (r - l > 1) {
            int m = (l + r) / 2;
            if (v[m].first <= v[i].first + 2 * D) {
                l = m;
            } else {
                r = m;
            }
        }
        
        ll t = st.query(i, i + 1);
        if (v[i].second > t) {
            ll x = v[i].second - t;
            ll d = (x + A - 1) / A;
            ans += d;
            st.add(i, l + 1, d * A);
        }
    }
    cout << ans << "\n";
    return 0;
}