AtCoder BC 095 D: Static Sushi

AtCoder

問題

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

解法

寿司の数が105なので、O(N)であれば間にいそう。ということで、まずは全探索で考えてみる。

考えられるパターンは以下の4ケースに分けられる。

ケース1：時計回りに何個か寿司を食べてそのまま終了する ケース2：時計回りに何個か寿司を食べてからスタート位置に戻り、反時計回りに何個か寿司を食べる ケース3：反時計回りに何個か寿司を食べてそのまま終了する ケース4：反時計回りに何個か寿司を食べてからスタート位置に戻り、時計回りに何個か寿司を食べる

ケース3と4はケース1と2を逆方向にしただけなので、以下ではケース1と2を考える。

ケース1は最大でN個まで寿司を食べる組み合わせしかないのでO(N)で探索可能。

ケース2については、最初に時計回りにi番目まで食べるとすると、スタート位置に戻ってから残ったN-i個の寿司のどこまで食べるかでN-i通り考えられる。

これをそのまま計算するとO(N2)となってしまい部分点しかもらえない。

そこで、事前に残っている寿司がk個の場合にどこまで食べるると最大になるかをkに対して求めておく。 そうすることで、スタート地点に戻ってからの計算量をO(1)に下げることが出来るので、全体としてO(N)に収めることが出来る。

なお、寿司のカロリーについては最初に累積和を求めておき、部分和をO(1)で算出できるようにしておく。

実装

ケース3と4はケース1と2と同じ事を逆方向に実装するだけだが、vとxのベクトルを逆方向にする（vは逆順に並べ換え、xはCから引いてから逆順に並べかえ）ことでケース1と2のロジックを流用できるかなと思ったが、素直にそのまま実装してしまった。

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<cmath>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)

using namespace std;

typedef long long int ll;

const ll INF=(ll)1e18;

int main(){
    int N;
    ll C;

    cin >> N >> C;

    vector<ll> x(N+1), v(N+1), vc(N+1);
    x[0] = 0;
    v[0] = 0;
    FOR(i,1,N+1)cin >> x[i] >> v[i];

    //vの累積和を求める
    vc[0] = v[0];
    FOR(i,1,N+1){
        vc[i] = vc[i-1] + v[i];
    }

    vector<ll> r(N+1);
    r[0] = 0;
    for(int i = 1; i <= N; i++){
        r[i] = max(r[i-1], vc[i]-x[i]);
    }

    vector<ll> l(N+1);
    l[N] = vc[N] - vc[N-1] - (C-x[N]);

    for(int i = N-1; i >= 1; i--){
        l[i] = max(l[i+1], vc[N]-vc[i-1]-(C-x[i]));
    }

    ll ans = 0;
    REP(i,N+1){
        //ケース1
        ll tmp = vc[i] -  x[i];
        if(tmp > ans)ans = tmp ;

        //ケース2
        if(i < N){
            tmp = vc[i] - 2 * x[i] + l[i+1];
            if(tmp > ans)ans = tmp ;
        }
    }

    for(int i = N; i >= 1; i--){
        //ケース3
        ll tmp = vc[N] -  vc[i-1] - (C - x[i]);
        if(tmp > ans)ans = tmp ;

        //ケース4
        tmp = vc[N] - vc[i-1] - 2 * (C - x[i]) + r[i-1];
        if(tmp > ans)ans = tmp ;
    }
    cout << ans << endl;
}