2017-08-30

AOJ 0553 ダンジョン の解説

解説

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0553

考察

問題点

あり本にある優先度キューを用いたガソリン問題と似ています。 ただし、こちらの問題では、ガソリンを入れられる量の上限があります。

体力が0以下になる前に、どこかで回復しなければいけない  ->どうせ回復するなら一番回復量が多い泉を使いたい   ->体力が0以下になった時に、最も回復量が高い泉を使ったことにすれば良い

これは優先度キューを用いれば実現できそうです。

やっかいなのは体力の上限で、「泉の回復量は多いが、体力が減っていないため、実際の回復量が小さくなる」ということが起きるため、優先度キューだけを用いてもうまくいきません。 「泉の回復量が多い順」ではなく、「実際の回復量が多い順」に並べなければいけません。

実際の回復量は、体力と泉の回復量がわかれば求めることができそうです。 そこで、各階を訪れた際の体力を持っておき、それを元に「実際の回復量」を決めましょう。

実際の回復量を求める

体力の更新方法をまずは考えます。

地下 i 階で体力が0になったので、地下 j 階で泉を使ったことにする( i > j )。 すると、当然地下 j 階〜 i 階の体力は増えます。つまり、区間に対する加算を行う必要があります。

また、加算した際に、体力が上限を超えてはいけません。 つまり、地下 j 階で体力を回復する場合、地下 j 階〜 i 階の区間のすべての体力は、(体力の上限 - j 階の回復量)以下である必要があります。 裏を返せば、地下 j 階の回復量は、(体力の上限 - 地下 j 階〜 i 階の区間で最大の体力)以下になります。

よって、実際の回復量を求めるためには、区間の最大値を求める必要があることがわかります。

方針

使うもの  優先度キュー、 セグメントツリー(区間に対する加算、 区間の最小値を求める)

1)体力をセグメントツリーに記録する 2)泉の情報をキューに入れる 3)体力を消費する 4)体力が0以下になったとき  1)最も回復量が多いものを取り出す  2)区間[回復する場所、現在地]の最大値を求める  3)体力の最大値 + 回復量 <= 体力の上限 のとき、その泉を使えるだけ使う。    使えないとき、実際の回復量を更新してキューに戻す。その後、1に戻る  4)泉を使って回復したことにし、区間に加算する。

実装

#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
//const int INF = 1e8;
using namespace std;

#define int long long

const int MAX_N = 100010;

class segTree{
    public:
        int n, dat[4 * MAX_N];
        void init(int n_, int value, int dat_b[4 * MAX_N] = NULL){
            n = 1;
            while(n < n_) n *= 2;
            rep(i,2 * n){
                dat[i] = value;
                if(dat_b != NULL) dat_b[i] = value;
            }
        }
        void output(int a[4 * MAX_N]){
            show("print");
            range(i,1,n * 2) cout << (a[i] == INT_MAX ? 0 : a[i]) << ' ';
            cout << endl;
        }
};

class starrySky : public segTree{
    private:
        int query(int a, int b, int k, int l, int r){
            if(b <= l || r <= a) return 0;
            if(a <= l && r <= b) return dat[k] + dat_add[k];

            int vl = query(a, b, k * 2, l, (l + r) / 2);
            int vr = query(a, b, k * 2 + 1, (l + r) / 2, r);
            return max(vl, vr) + dat_add[k];
        }
        void add(int a, int b, int k, int l, int r, int x){
            if(b <= l || r <= a) return;
            if(a <= l && r <= b){
                dat_add[k] += x;
            }else{
                add(a, b, k * 2, l, (l + r) / 2, x);
                add(a, b, k * 2 + 1, (l + r) / 2, r, x);
                dat[k] = max(dat[k * 2] + dat_add[k * 2], dat[k * 2 + 1] + dat_add[k * 2 + 1]);
            }
        }
        void init(int n_){ segTree::init(n_,0,dat_add); }
    public:
        int dat_add[4 * MAX_N];
        starrySky(int n){ init(n); }
        int query(int a, int b){ return query(a, b, 1, 0, n); }
        void add(int s, int t, int x){ add(s, t, 1, 0, n, x); }
        void add(int i, int x){ add(i, i + 1, 1, 0, n, x); }
};


signed main(){
    long long n, h;
    cin >> n >> h;

 //1-indexのセグ木
    starrySky seg(n); //体力を保持する
    priority_queue<pair<long long, int>> q; //泉の回復量、pos
    long long cur = h, ans = 0;
    rep(i,n - 1){
        long long damage, heal;
        cin >> damage >> heal;
        q.push(make_pair(heal, i));

        seg.add(i + 1, cur);
        cur -= damage;
        while(cur <= 0){
            pair<long long, int> use = q.top(); q.pop();
            long long maxHP = seg.query(use.second + 1, i + 2); //回復地点から現在地までの体力の最大
    
            if(maxHP + use.first > h){ //回復量が上限を超えるので、実際の回復量に変更
                q.push(make_pair(h - maxHP, use.second));
                continue;
            }
    
            long long can_use = (h - maxHP) / use.first;
            long long require = ceil((-1.0 * cur + 1) / use.first);
            long long used = min(can_use, require);
            ans += used;
            cur += used * use.first;
    
            seg.add(use.second + 1, i + 2, used * use.first);
            q.push(use);
        }
    }
    cout << ans << endl;
}