Codeforces Round #219 (Div. 1) C. Watching Fireworks is Fun

問題

codeforces.com

解法

普通に dp しようと考えると,
dp[m][n] = (m 個目の花火の時座標 n にいるような場合で, 喜び度の max 値) というのが考えられて, これは
dp[m][n] = (dp[m][n-diff], dp[m][n-diff+1], ..., dp[m][n+diff] の最小値) + abs(A[m]-n) と書けます。

最小値は区間的になっているので, segment tree で大勝利, かと思ったんですが n*m の時点で結構きついので O(nm log n) だと間に合いません。ということで, O(nm) にすることを考えるんですが, slidng window minimum というアルゴリズムを使うとこれを実現できます。
Sliding Window Minimum Implementations
しゃくとりと少し似てる…けどこちらは「区間の長さが常に一定」とわかってる時に特に使えるアルゴリズムですね。

deque で区間の最小値を持っておくんですが, deque の先頭から順番に小さい順に並んでいるようにしておきます。

[j-diff, j] の区間における最小値を考えるときは, まず j 番目の値より大きいものはすべて後ろから取り除いていきます。
で, deque に入れるときに, array[j] の値だけでなく 座標値 j も入れておけば, j-diff よりも小さい座標値は deque.pop_front() で消していけるので, [j-diff, j] の最小値を deque.front() で得ることが出来ます。

今回の問題では, [j-diff, j+diff] の範囲の最小値が欲しいので, dp に n 個の INF 要素を付け加えたものに対して sliding window minimum をやりました。

sliding window っていう名前も良く出来てますね。同じ長さの区間に対して 1 つずつスライドさせるイメージが湧きやすい気がする。

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    const ll INF = 1ll<<55;
    int n, m, d;
    cin >> n >> m >> d;
    vector<int> A(m), B(m), T(m);
    for (int i = 0; i < m; i++) {
        cin >> A[i] >> B[i] >> T[i];
    }
    vector<ll> dp(n+1);
    for (int i = 0; i < m; i++) {
        vector<ll> _dp(n+1);
        int dt = T[i];
        if (i > 0) dt -= T[i-1];
        int diff = min<ll>(n-1, (ll)dt*d);
        deque<pii> window;
        vector<ll> memo(2*n+1);
        for (int j = 0; j < n; j++) dp.push_back(INF);
        for (int j = 1; j <= 2*n; j++) {
            while (!window.empty() && window.back().first >= dp[j]) window.pop_back();
            window.emplace_back(dp[j], j);
            while (window.front().second < j-2*diff) window.pop_front();
            memo[j] = window.front().first;
        }
        for (int j = 1; j <= n; j++) {
            _dp[j] = memo[j+diff] + abs(A[i]-j);
        }
        dp = _dp;
    }
    ll ans = INF;
    for (int i = 1; i <= n; i++) ans = min(ans, dp[i]);
    ll sum = 0;
    for (int i = 0; i < m; i++) sum += B[i];
    cout << sum-ans << endl;
    return 0;
}