CS Academy #46 (Div. 1.5) E - Ultimate Orbs

https://csacademy.com/contest/round-46/task/ultimateorbs/

問題概要

N個のオーブが座標1~Nに順番に並んでいる。各オーブには強さGiが設定されており、左隣あるいは右隣のオーブに対して 自分の強さ+D >= 相手の強さ であればそのオーブを吸収できる。吸収した側のオーブは強さの値が相手の強さ分増え、された側は消滅する。(N-1)回の吸収が起こったとき最終的に残る可能性のあるオーブをすべて挙げよ。

1 <= N <= 106

0 <= D <= 109

0 <= Gi <= 109

解法

まず数列の中で最大の強さをもつオーブは明らかに他のオーブを全部吸収できる。ここでその最大のオーブを境界にして数列を左右に分割してみる(ただし境界はどちらにも含めない)と、分割後数列の最大値は明らかに区間内の他の値を全部吸収できる。そして吸収した結果、境界を吸収できるほどの強さになっていればその要素は境界を越えて数列全体を吸収できることになる。もし境界を越えられないのであれば、そのオーブはもちろん区間内の他のオーブも全部ボツになる(最大値が無理なら他のも自明に無理なので)。逆にもし越えられるのであれば、その要素を新たに境界として区間を分割する。この操作を繰り返していくと各区間には「左の境界」と「右の境界」ができていくことになるが、このうちどちらかでも越えられるなら全部の要素を吸収できるとしてよい。なぜなら境界となりえる数値は既に他の値を全部吸収できることが保証されており、そのような値を吸収できる値もまた他の値を全部吸収できるからである。

上で説明したような手続きを実際にプログラムに落とすと以下のような感じになる。

  1. キューから区間を取り出す(区間には左の境界の値、右の境界の値も記録しておく)
  2. 区間の総和をとり、左右どちらかの境界を越えられているかチェックする
  3. もし越えられていなければその区間内のインデックスをすべて×にして1に戻る
  4. 区間の最大値とそのインデックスを得、そのインデックスを境界として区間を分割しキューに追加する
  5. キューに区間が残っていれば1に戻る
  6. ×がついていないオーブを答えとして出力する

区間の総和は累積和を計算しておけばO(1)でできる。区間の最大値はいろいろあるけどセグ木でO(logN)でできる。セグ木はpairとかでインデックスも持つようにすると最大値だけじゃなくてそのインデックスも取ってくるようにできる。この場合和をセグ木にしてもオーダーは変わらないが、この問題はN<=106でO(NlogN)がかなりギリギリなのでその辺頑張らないと通らなかった。(最初は和も最大値もセグ木で最大値の方は値取得→unordered_mapに溜めといた強さごとのインデックス表を二分探索とか悠長なことしてたがTLE祭りだった)

感想

なんか途中ヴェルタースオリジナルみたいになった

コード (C++)

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for (int i=0;i<(n);i++)
#define REP2(i,m,n) for (int i=m;i<(n);i++)
typedef long long ll;



class SegmentTreeMax {
public:
    vector<pair<ll, int>> table;
    int size;

    SegmentTreeMax(int n) {
        size = 1;
        while (size <= n) size *= 2;
        size *= 2;
        table = vector<pair<ll, int>>(size, make_pair(-1, -1));
    }

    void assign(int pos, ll num) {
        return assign(pos, num, 0, 0, size/2-1);
    }

    void assign(int pos, ll num, int i, int left, int right) {
        if (left == right) {
            table[i] = make_pair(num, pos);
            return;
        }
        auto mid = (left + right) / 2;
        if (pos <= mid)
            assign(pos, num, i*2+1, left, mid);
        else
            assign(pos, num, i*2+2, mid+1, right);

        if (table[i*2+1].first >= table[i*2+2].first) 
            table[i] = table[i*2+1];
        else
            table[i] = table[i*2+2];
    }

    int query(int pl, int pr) {
        return query(pl, pr, 0, 0, size/2-1).second;
    }

    pair<ll, int> query(int pl, int pr, int i, int left, int right) {
        if (pl > right || pr < left)
            return make_pair(-1, -1);
        else if (pl <= left && right <= pr)
            return table[i];

        pair<ll, int> q1 = query(pl, pr, i*2+1, left, (left+right)/2);
        pair<ll, int> q2 = query(pl, pr, i*2+2, (left+right)/2+1, right);
        return q1.first >= q2.first ? q1 : q2;
    }
};




ll A[1000010];
ll B[1000010];
bool ok[1000010];

ll sumq(int l, int r) {
    return B[r+1] - B[l];
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);

    memset(B, 0, sizeof(B));
    memset(ok, 0, sizeof(ok));

    int N;
    ll D;
    cin >> N >> D;
    REP(i, N) cin >> A[i];
    REP(i, N) B[i+1] = B[i] + A[i];

    SegmentTreeMax stmax = SegmentTreeMax(N);
    REP(i, N) stmax.assign(i, A[i]);

    deque<tuple<ll, int, int, ll, ll>> q;
    q.push_back(make_tuple(stmax.query(0, N-1), 0, N-1, -1, -1));

    while (!q.empty()) {
        auto t = q.front();
        int m = get<0>(t);
        int l = get<1>(t);
        int r = get<2>(t);
        ll lv = get<3>(t);
        ll rv = get<4>(t);
        q.pop_front();

        ll s = sumq(l, r);
        if (s + D < lv && s + D < rv) {
            REP2(i, l, r+1) ok[i] = false;
            continue;
        }

        ok[m] = true;

        ll nlv = lv == -1 ? (1LL << 59) : lv;
        ll nrv = rv == -1 ? (1LL << 59) : rv;

        if (m > l)
            q.push_back(make_tuple(stmax.query(l, m - 1), l, m - 1, nlv, A[m]));
        if (m < r)
            q.push_back(make_tuple(stmax.query(m + 1, r), m + 1, r, A[m], nrv));
    }


    REP(i, N) if (ok[i]) cout << i + 1 << " ";
    cout << endl;

    return 0;
}