問題概要

えびちゃんのお気に入り問題の一つなので人々に解いてみてほしいhttps://t.co/mflgdhqEVH pic.twitter.com/aVVI23MM3R
— えびちゃん (@rsk0315_h4x) 2020年1月2日

rsk0315 さんのツイートについている画像があまりにもわかりやすすぎる．

解法概要

スコアの最大値の式を作っていじってみる．なお，式中の s, tは区間 [s, t] を選んだということに対応する．

t の影響する部分を固める感じで変形していくと，

$$\begin{aligned}&\max_{s, t} \left( \sum_{i=s}^t (i-(s-1)) a_i \right) \\ &= \max_{s, t} \left( \sum_{i=s}^t (i+1) a_i - s \sum_{i=s}^t a_i \right) \\ &= \max_{s, t} \left( \left(- s \sum_{i=1}^t a_i + \sum_{i=1}^t (i+1) a_i \right) - \sum_{i=1}^{s-1} (i+1) a_i + s \sum_{i=1}^{s-1} a_i \right) \\ &= \max_{s} \left( \max_{t} \left(- s \sum_{i=1}^t a_i + \sum_{i=1}^t (i+1) a_i \right) - \sum_{i=1}^{s-1} (i+1) a_i + s \sum_{i=1}^{s-1} a_i \right) \end{aligned}$$

このように t について関係ある部分を最大化した後にその結果を使って s について最大化するような式になる．

したがって，s を変数とする t 本の直線 $ - s \sum_{i=1}^t a_i + \sum_{i=1}^t (i+1) a_i $ について，各 s についての最大値を求めるために Convex Hull Trick が使える．

注意するべきことは，直線の傾きである$\sum_{i=1}^t a_i $ は t に対して単調ではないということである ( ai が負になりうるため) ．そのため，よく知られている直線の傾きの単調性を使う Convex Hull Trick は使えない．

ここで使えるのが Li-Chao Tree である．Li-Chao Tree は一言で言うと Convex Hull Trick の対象となる直線を管理する Segment Tree である． Li-Chao Tree 自体の実装方法は Li Chao Treeのメモ - 日々ｄｒｄｒする人のメモを参考にさせていただいた．

あとはその結果を使って $ \left( \max_{t} \left(- s \sum_{i=1}^t a_i + \sum_{i=1}^t (i+1) a_i \right) - \sum_{i=1}^{s-1} (i+1) a_i + s \sum_{i=1}^{s-1} a_i \right)$ を求める，という計算を n 回繰り返し，最大の値を答えとすれば良い．

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

using ll =  long long;
using Pll = pair<ll, ll>;

constexpr int N_MAX = 200000;
constexpr int INF = 1 << 30;
constexpr ll LINF = 1LL << 60;

class LiChaoTree {
public: 
    int n, xi = 0;
    vector<Pll> data;
    vector<ll> xs;
    ll def;

    LiChaoTree(int _n, ll _def=0LL): def(_def) {
        n = 1;
        while(n < _n) n <<= 1;
        data.assign(2*n-1, {0, LINF});
        xs.assign(n, INF);
    }

    ll f(Pll line, ll x) {
        return line.first * x + line.second;
    }

    // 線分追加前に点を追加しておく (昇順)
    void add_point(ll x) {
        xs[xi++] = x;
    }

    // y = grad * x + intercept を追加
    void add_line(ll grad, ll intercept) {
        _add_line({grad, intercept}, 0, 0, n);
    }

    // 座標 x での最大値
    ll find(ll x) {
        int xi = distance(xs.begin(), lower_bound(xs.begin(), xs.end(), x));
        xi += n-1;
        ll ret = def;
        if(data[xi].first != 0 || data[xi].second != LINF) {
                ret = f(data[xi], x);
        }
        while(xi) {
            xi = (xi-1) / 2;
            if(data[xi].first != 0 || data[xi].second != LINF) {
                ret = max(ret, f(data[xi], x));
            }
        }
        return ret;
    }

private: 
    void _add_line(Pll line, int k, int kl, int kr) {
        int kc = (kl+kr) / 2;
        // データなしなら line を追加
        if(data[k].first == 0 && data[k].second == LINF) {
            data[k] = line;
            return;
        }

        ll xl = xs[kl], xc = xs[kc], xr = xs[kr-1];
        bool comparison_left = (f(line, xl) > f(data[k], xl));
        bool comparison_mid  = (f(line, xc) > f(data[k], xc));
        bool comparison_right= (f(line, xr) > f(data[k], xr));

        // 全部で line の方が小さければ line は捨てる
        if(!comparison_left && !comparison_right) {
            return;
        }
        // 全部で line の方が大きければ line を採用
        if(comparison_left && comparison_right) {
            data[k] = line;
            return;
        }
        // 区間の半分以上で line の方が大きければ data[k] と交換して続ける
        if(comparison_mid) {
            swap(line, data[k]);
        }

        // 右側ではもう最大値を取り得ないが，左側ではまだ取りうる場合
        if(comparison_left != comparison_mid) {
            _add_line(line, 2*k+1, kl, kc);
            return;
        }

        // 左側では最大値を取り得ないが，右側ではまだ取りうる場合
        if(comparison_right != comparison_mid) {
            _add_line(line, 2*k+2, kc, kr);
            return;
        }

        return;
    }

};
 
int main() {
    int n;
    cin >> n;
    vector<ll> a(n+1, 0), i1_ai_sum(n+1, 0), ai_sum(n+1, 0);
    for(int i=1;i<=n;++i) {
        cin >> a[i];
        ai_sum[i] = ai_sum[i-1] + a[i];
        i1_ai_sum[i] = i1_ai_sum[i-1] + (i+1) * a[i]; 
    }

    LiChaoTree tree = LiChaoTree(n, -LINF);

    for(int s=1;s<=n;++s) tree.add_point(s);

    ll ans = 0LL;
    for(int s=n;s>=1;--s) {
        tree.add_line(-ai_sum[s], i1_ai_sum[s]);
        ll tmp = tree.find(s) - i1_ai_sum[s-1] + s * ai_sum[s-1];
        ans = max(ans, tmp);
    }
    cout << ans << endl;
}

所感

前回の記事を書いてから，rsk0315 さんにお勧めしてもらった問題．

そもそも Convex Hull Trick を使う発想が出なかった前回とは異なり．今回は Convex Hull Trick が使える形に直してからが長かった．

今回実装した Li-Chao Tree もSegment Tree みたいに抽象化しないとな．

NoiminのNoise

Educational Codeforces Round 11 F. Bear and Bowling 4

問題概要

解法概要

ソースコード

所感