AtCoder Regular Contest 056 D - サケノミ

問題

arc056.contest.atcoder.jp

解法

kmjp さんの解法を参考にしました。
kmjp.hatenablog.jp

dp[t] = (「t の時間に飲む」と決めたとき, t の時間までに得られる美味しさの総和の最大値)とします。

部分点解法では, t の前に飲む時間 t1 を全探索します。t1 - t の間に注がれる酒の分だけ美味しさが増減しますが, それを調べれば部分点は取れます(t-1, t-2, ... というように見ていって, だんだん考慮する酒が増えていくイメージ)。

満点解法では, もうちょっと賢くやります。dp[t] を求めたいときどうするかを考えるのですが, 上記の計算が「区間の最大値」を計算していることを考えると, セグメント木っぽくしたいです。ある酒 i が時刻 t で注がれるとき, その直前に酒 i が注がれるのが t1 である場合, t1 <= T < t の間に最後に酒を飲んでいた場合, 酒 i は新たに注がれることになります。これを区間で表現する場合, 「[t1, t) の区間に W[i] を加える」とすれば良さそうです。

つまり, 「区間add, 区間max」というクエリを高速に処理できるセグメント木を用意すれば良いです。やり方なんですが, maxi[k] = (対応する区間の max 値), val[k] = (対応する区間で一様に足すことが分かっている値) とします。

すると, update(a, b, v) ([a, b) の区間に v を足す) というのは,

• もし 区間 [l, r) が [a, b) を完全に含んでいるなら, val[k] += v, maxi[k] += v とやって吸収させる
• そうでないなら, さらに細かく区間を見て, maxi[k] = max(maxi[2*k+1], maxi[2*k+2])+val[k] とする(val[k] は今までに吸収した値分を足しこんでる感じ)

で OK です。全体の最大値は毎回 maxi[0] を見れば良いですね。

const ll INF = 1ll<<60;

class Segtree {
public:
    Segtree(int N) {
        size = 1;
        while (size <= N) size *= 2;
        val.resize(2*size); maxi.resize(2*size, -INF);
    }
    // 区間 [a, b) に値 v を加算
    void update(int a, int b, ll v, int k, int l, int r) {
        if (b <= l || a >= r) return;
        if (a <= l && r <= b) {
            val[k] += v;
            maxi[k] += v;
        } else {
            update(a, b, v, 2*k+1, l, (l+r)/2);
            update(a, b, v, 2*k+2, (l+r)/2, r);
            maxi[k] = max(maxi[2*k+1], maxi[2*k+2]) + val[k];
        }
    }
    void update(int a, int b, ll v) {
        update(a, b, v, 0, 0, size);
    }
    vector<ll> val, maxi;
    int size;
};

const int MAXN = 1001000;
int W[MAXN];
int pre[MAXN];
vi drink[MAXN];
ll dp[MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> W[i];
    }
    for (int i = 0; i < N; i++) {
        int M;
        cin >> M;
        for (int j = 0; j < M; j++) {
            int t;
            cin >> t;
            drink[t].push_back(i);
        }
    }
    Segtree seg(MAXN);
    dp[0] = 0;
    seg.update(0, 1, INF+dp[0]);
    ll ans = 0;
    for (int t = 2; t < MAXN; t++) {
        for (int d : drink[t]) {
            seg.update(pre[d], t, W[d]);
            pre[d] = t;
        }
        dp[t] = seg.maxi[0];
        seg.update(t, t+1, INF+dp[t]);
        ans = max(ans, dp[t]);
    }
    cout << ans << endl;
    return 0;
}