AtCoder Regular Contest 056: D - サケノミ

,

http://arc056.contest.atcoder.jp/tasks/arc056_d

solution

動的計画法。時刻$t$でグラスが全て空なとき(それ以前はなかったことにして)それ以降を最適に飲んだときの美味しさの総和の最大値を$\mathrm{dp}_t$とする。 単純には後ろからそのまま計算していき$T = \max t_{i,j}$に対し$O(T^2 \sum M_i)$。 漸化式は$\mathrm{dp}_t = \max \{ \mathrm{drinks}[t, t’) + \mathrm{dp}_{t’} \mid t \lt t’ \}$だが、$\mathrm{dp’}_{\bullet,t’} = \mathrm{drinks}[\bullet, t’) + \mathrm{dp}_{t’}$と取りなおして区間add/区間maxのsegment木でまとめて管理すれば$O(T \log T + \sum M_i)$。

implementation

遅延伝播segment木をmonoid/magma準同型で整理したらすごく良かった。 座圧は必須でない。

#include <cstdio>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
#include <type_traits>
#include <cassert>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_reverse(i,n) for (int i = (n)-1; (i) >= 0; --(i))
#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using ll = long long;
using namespace std;

template <typename T>
map<T,int> coordinate_compression_map(vector<T> const & xs) {
    int n = xs.size();
    vector<int> ys(n);
    whole(iota, ys, 0);
    whole(sort, ys, [&](int i, int j) { return xs[i] < xs[j]; });
    map<T,int> f;
    for (int i : ys) {
        if (not f.count(xs[i])) { // make unique
            int j = f.size();
            f[xs[i]] = j; // f[xs[i]] has a side effect, increasing the f.size()
        }
    }
    return f;
}

template <class Monoid, class MagmaEndomorphism>
struct lazy_propagation_segment_tree { // on monoids
    static_assert (is_same<typename Monoid::type, typename MagmaEndomorphism::underlying_type>::value, "");
    typedef typename Monoid::type T;
    typedef typename MagmaEndomorphism::type F;
    Monoid mon;
    MagmaEndomorphism endo;
    int n;
    vector<T> a;
    vector<F> f;
    lazy_propagation_segment_tree() = default;
    lazy_propagation_segment_tree(int a_n, Monoid const & a_mon = Monoid(), MagmaEndomorphism const & a_endo = MagmaEndomorphism())
            : mon(a_mon), endo(a_endo) {
        n = 1; while (n <= a_n) n *= 2;
        a.resize(2*n-1, mon.unit());
        f.resize(max(0, 2*n-1-n), endo.identity());
    }
    void range_apply(int l, int r, F z) {
        assert (0 <= l and l <= r and r <= n);
        range_apply(0, 0, n, l, r, z);
    }
    void range_apply(int i, int il, int ir, int l, int r, F z) {
        if (l <= il and ir <= r) {
            a[i] = endo.apply(z, a[i]);
            if (i < f.size()) f[i] = endo.compose(z, f[i]);
        } else if (ir <= l or r <= il) {
            // nop
        } else {
            range_apply(2*i+1, il, (il+ir)/2, 0, n, f[i]);
            range_apply(2*i+1, il, (il+ir)/2, l, r, z);
            range_apply(2*i+2, (il+ir)/2, ir, 0, n, f[i]);
            range_apply(2*i+2, (il+ir)/2, ir, l, r, z);
            a[i] = mon.append(a[2*i+1], a[2*i+2]);
            f[i] = endo.identity();
        }
    }
    T range_concat(int l, int r) {
        assert (0 <= l and l <= r and r <= n);
        return range_concat(0, 0, n, l, r);
    }
    T range_concat(int i, int il, int ir, int l, int r) {
        if (l <= il and ir <= r) {
            return a[i];
        } else if (ir <= l or r <= il) {
            return mon.unit();
        } else {
            return endo.apply(f[i], mon.append(
                    range_concat(2*i+1, il, (il+ir)/2, l, r),
                    range_concat(2*i+2, (il+ir)/2, ir, l, r)));
        }
    }
};

struct max_t {
    typedef ll type;
    ll unit() const { return 0; }
    ll append(ll a, ll b) const { return max(a, b); }
};

struct plus_endomorphism_t {
    typedef ll underlying_type;
    typedef ll type;
    type identity() const {
        return 0;
    }
    type compose(type a, type b) const {
        return a + b;
    }
    underlying_type apply(type a, underlying_type b) const {
        return a + b;
    }
};

int main() {
    // input
    int n; scanf("%d", &n);
    vector<int> w(n); repeat (i, n) scanf("%d", &w[i]);
    vector<vector<int> > t(n);
    repeat (i, n) {
        int m; scanf("%d", &m);
        t[i].resize(m);
        repeat (j, m) scanf("%d", &t[i][j]);
    }
    // solve
    map<int, int> compress; {
        vector<int> xs;
        repeat (i, n) {
            xs.insert(xs.end(), t[i].begin(), t[i].end());
        }
        compress = coordinate_compression_map(xs);
    }
    int t_size = compress.size();
    vector<vector<int> > at(t_size);
    repeat (i, n) {
        repeat (j, t[i].size()) {
            at[compress[t[i][j]]].push_back(i);
        }
    }
    lazy_propagation_segment_tree<max_t, plus_endomorphism_t> segtree(t_size + 1);
    vector<int> last(n, t_size);
    repeat_reverse (i, t_size) {
        for (int k : at[i]) {
            segtree.range_apply(i+1, last[k] + 1, w[k]);
            last[k] = i;
        }
        ll acc = max(0ll, segtree.range_concat(i+1, t_size + 1));
        segtree.range_apply(i, i+1, acc);
    }
    // output
    ll result = segtree.range_concat(0, 0+1);
    printf("%lld\n", result);
    return 0;
}