Static Sushi [AtCoder Regular Contest 096 D]

https://beta.atcoder.jp/contests/arc096/tasks/arc096_b

考察過程

1. 貪欲に動くことを考えてみると、「→に動いて寿司を取ったら出る」の中で最大が答え？
2. サンプルで落ちる「逆向きにも移動できる」
3. もうちょっと貪欲を改善する「→に動いて寿司を取って、←に動いて寿司を取って出る」の中で最大が答え？
4. これは「片方を固定して、もう片方は最適を高速に探す」テクを累積和とか累積maxとかで上手くやれる
5. またサンプルで落ちる「←に動いて→に動く方が最適な場合もある」
6. 逆サイドは入力が時計回りになっているので、逆時計回りにしてもう一回同じ貪欲をやる
7. これでAC

解法

https://beta.atcoder.jp/contests/arc096/submissions/2391100

今の位置から、→に移動して寿司を取り、←に移動して寿司を取って出る行動の中で最適のものを返そう。
このために「右端を固定して、左端の最適を高速に探す」テクを使うことで計算していこう。

右端はi番目の寿司までを取るとして説明する。（以下、for文内部の説明）
まず時計回りに移動してi番目の寿司まで取る。
移動し終えたらそれまでのカロリーを摂取する（これは累積和でO(1)）
次に、最初の場所に戻る。
そこから←に移動して帰るが、事前に最適な答えを見つけたおこう。
　
最適な答え
D[i] := N-1番目からi番目までの寿司を食べられる時のカロリー差の最大値
これは
D[i] := i番目までの寿司を食べる時のカロリー差の最大値
をまず計算して累積和の要領でmaxを取って累積maxすることで実現できる。

int N; ll C;
ll x[101010], v[101010];
ll y[101010];
ll A[101010], B[101010], D[101010];
//---------------------------------------------------------------------------------------------------
ll solve() {
    A[0] = v[0];
    rep(i, 1, N) A[i] = A[i - 1] + v[i];
 
    rep(i, 0, N) y[i] = C - x[i];
    B[N - 1] = v[N - 1];
    rrep(i, N - 2, 0) B[i] = B[i + 1] + v[i];
 
    D[N - 1] = B[N - 1] - y[N - 1];
    rrep(i, N - 2, 0) {
        D[i] = B[i] - y[i];
        chmax(D[i], D[i + 1]);
    }
 
 
    ll ans = 0;
    rep(i, 0, N) {
        ll sm = 0;
 
        sm -= x[i]; // →移動
        sm += A[i]; // →カロリー
        chmax(ans, sm);
 
        sm -= x[i]; // 原点に戻る
 
        if (i < N - 1) sm += D[i + 1];
 
        chmax(ans, sm);
    }
    
    return ans;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> C;
    rep(i, 0, N) cin >> x[i] >> v[i];
    
    ll ans = 0;
    chmax(ans, solve());
 
    reverse(v, v + N);
    rep(i, 0, N) x[i] = C - x[i];
    reverse(x, x + N);
 
    chmax(ans, solve());
    cout << ans << endl;
}