https://atcoder.jp/contests/dp/tasks/dp_w

問題概要

'0'と'1'のみからなる長さNの文字列を考える。M個のスコア条件(l, r, a)が与えられたとき、文字列の区間[l, r]のうち少なくとも1文字が'1'であればa点を得る。文字列を自由に構成できるとき、スコアの最大値を求めよ。

N, M <= 2*10⁵

-10⁹ <= a <= 10⁹

解法

文字列を左から構成していくものとして、以下のDPを考える。

dp(i): 最後に'1'を置いたのがi文字目であるときの最大スコア

dp[i]の値を決めるときのことを考えてみる。もしiに被っている区間が [x, y] のひとつだけで、この区間のスコアがaだったとすると、遷移は以下のようになる。

dp[i] = max( max(dp[0〜x-1] + a), max(dp[x〜i-1]) )

この式は「もし最後に1を置いたのがxより前であるなら、ここで1を置いたとき初めて[x, y]が有効になって自動的にa点が入る」と「既にx〜i-1のどこかに1を置いているのでiに新たに1を置いても何も起こらない」の2パターンを見て大きい方を取る、ということを表している。（dp[i]ではiに1を置いたときのことを考えているので、どちらが取られるにせよaの値は織り込まれているという点に注意する）

ひとつのiに対して被る区間が複数ある場合でも考え方は同じ（「区間が被らない場所から遷移してくる場合にはその区間の点数を足す」「区間が被っている場所から遷移してくる場合には点数は足さない」）。つまり現在のiに被っているすべての区間[x, y]について、dp[0] 〜 dp[x-1]に一律にその区間の点数を足しておいた上で、dp[0〜i-1]までのmaxをとるとdp[i]の値となる。

これは尺取りみたいなやつとかで現在のiに被っている区間を管理しつつ、新たな区間[x, y]が入ってきたらdp[0]〜dp[x-1]にスコアを加算する、抜ける区間があったらdp[0]〜dp[x-1]から最初に足したぶんのスコアを引く、dp[i]の値にはdp[0]〜dp[i-1]のmaxを採用する、という操作で実現できる。区間加算、区間maxができればよいので遅延セグ木とかを使えばok.

解法

kmjpさんの解説を読んで解いた。既に確定しているはずの過去のdpテーブルの値を弄る、というところに凄い違和感があってなかなか腑に落ちなかったが、お気持ち的にはDPテーブルを活用して遷移の前計算をしているという風に捉えればいいんだろうか

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, core.stdc.string;

immutable long INF = 1L<<59;

void main() {
    auto s = readln.split.map!(to!int);
    auto N = s[0];
    auto M = s[1];
    auto LRA = M.iota.map!(_ => readln.split.map!(to!int).array).array;
    LRA.sort();

    auto st = new LazySegmentTree!(long, long, max, (a,b)=>a+b, (a,b)=>a+b, (a,b)=>a, -INF, 0L)(N+1);
    st.table[] = 0L;
    auto pq = new BinaryHeap!(Array!(Tuple!(int, int, long)), "a[1] > b[1]")();

    for (int i = 1, p = 0; i <= N; ++i) {
        while (p < M && i >= LRA[p][0]) {
            pq.insert(tuple(LRA[p][0], LRA[p][1], LRA[p][2].to!long));
            st.update(0, LRA[p][0]-1, LRA[p][2].to!long);
            ++p;
        }

        auto v = st.query(0, i-1);
        st.update(i, i, v);

        while (!pq.empty && pq.front[1] <= i) {
            st.update(0, pq.front[0]-1, -pq.front[2].to!long);
            pq.removeFront;
        }
    }

    st.query(0, N).writeln;
}



class LazySegmentTree(T, L, alias opTT, alias opTL, alias opLL, alias opPrd, T eT, L eL) {
    T[] table;
    L[] lazy_;
    int n;
    int size;

    this(int n) {
        this.n = n;
        size = 1;
        while (size <= n) size <<= 1;
        size <<= 1;
        table = new T[](size);
        lazy_ = new T[](size);
        table[] = eT;
        lazy_[] = eL;
    }

    void push(int i, int a, int b) {
        if (lazy_[i] == eL) return;
        table[i] = opTL(table[i], opPrd(lazy_[i], b - a + 1));
        if (i * 2 + 1 < size) {
            lazy_[i*2] = opLL(lazy_[i*2], lazy_[i]);
            lazy_[i*2+1] = opLL(lazy_[i*2+1], lazy_[i]);
        }
        lazy_[i] = eL;
    }

    T query(int l, int r) {
        if (l > r) return eT;
        return query(l, r, 1, 0, n-1);
    }

    T query(int l, int r, int i, int a, int b) {
        if (b < l || r < a) return eT;
        push(i, a, b);
        if (l <= a && b <= r) {
            return table[i];
        } else {
            return opTT(query(l, r, i*2, a, (a+b)/2), query(l, r, i*2+1, (a+b)/2+1, b));
        }
    }

    void update(int l, int r, L val) {
        if (l > r) return;
        update(l, r, 1, 0, n-1, val);
    }

    void update(int l, int r, int i, int a, int b, L val) {
        if (b < l || r < a) {
            push(i, a, b);
        } else if (l <= a && b <= r) {
            lazy_[i] = opLL(lazy_[i], val);
            push(i, a, b);
        } else {
            push(i, a, b);
            update(l, r, i*2, a, (a+b)/2, val);
            update(l, r, i*2+1, (a+b)/2+1, b, val);
            table[i] = opTT(table[i*2], table[i*2+1]);
        }
    }
}

nebukuro09の日記

Educational DP Contest / DP まとめコンテスト: W - Intervals

問題概要

解法

解法

コード (D言語)