CS Academy Ultimate Orbs

リンク : https://csacademy.com/contest/archive/task/ultimateorbs/statement/

問題概要

N個のオーブがある。それぞれのオーブは隣のオーブが自身のコスト+D以下だと、隣のオーブの重さを吸収する。それぞれのオーブに関して、自身が最後まで残ることができるかどうか調べよ。

解説

とりあえず、重さが最大のオーブは必ず残ることができる。あるオーブiから初めて、最大のオーブを吸収することができれば最後まで残ることができる。さらにこのオーブiを吸収できれば...と続けていけば、すべて求めることできる。flag[i]を最後になれるかどうかだとする。重さが最大の場合は1に初期化しておく。ではどのように探索すればよいか考える。オーブiから見ていって、自身より重い最寄りのオーブに関して考える。手前のものをL[i]、奥のものをR[i]とする。(L[i],R[i])の和+DがL[i]、R[i]の重さより重ければL[i]、R[i]から始めることができる。そうでない場合は始められない。このように探索していくと、それぞれのオーブについて1回しか探索しないことになる。そうすることによってO(N)で解ける。
再帰的に考える発想は難しい・・・

LL n, d, L[1100000], R[1100000], flag[1100000],sum[1100000], cnt;
Pll a[1100000];
bool func(int cur) {
    bool ret = 0;
    if (cur == -1 || cur == n)return 0;
    if (flag[cur] != -1)return flag[cur] == 1 ? 1 : 0;
    if (L[cur] == -1 && R[cur] == n)return flag[cur] = 1;
    LL num = sum[R[cur]] - sum[L[cur]+1] + d;
    if (num >= a[L[cur]].fir)ret |= func(L[cur]);
    if (num >= a[R[cur]].fir)ret |= func(R[cur]);
    return flag[cur] = ret;
}
int main() {
    cin >> n >> d;
    rep(i, n) {
        cin >> a[i].fir;
        a[i].sec = i;
        sum[i + 1] += sum[i] + a[i].fir;
        flag[i] = -1;
    }
    vector<Pll>vec;
    vec.push_back(Pll(INF, -1));
    rep(i, n) {
        while (vec.back().fir <= a[i].fir)vec.pop_back();
        L[i] = vec.back().sec;
        vec.push_back(a[i]);
    }
    vec.clear();
    vec.push_back(Pll(INF, n));
    Rrep(i, n) {
        while (vec.back().fir <= a[i].fir)vec.pop_back();
        R[i] = vec.back().sec;
        vec.push_back(a[i]);
    }
    rep(i, n) {
        if (func(i)) {
            if (cnt)cout << " ";
            cout << i + 1;
            cnt++;
        }
    }
    cout << endl;
    return 0;
}