AGC030 B Tree Burning

問題

atcoder.jp

解説

最初に半時計回りに進むと仮定してよい。(座標を反転させて同じ処理をした結果とmaxを取れば正しい結果が得られる)

このとき、最初に反時計周りにi個燃やして方向を逆にしないで進んだあとに各木を燃やす毎に方向を逆にしていくのが最適になる。(もし、方向転換を繰り返したあとに、特定方向に進みながら木を複数個燃やし、その後にまた方向転換すると最初に方向転換しながら進んでいた分を後に回すと1回方向転換する毎に進める距離が長くなるため。実験するとわかりやすい。)

故に最初に反時計周りにi個進み続けた後に、木を燃やすごとに方向転換する場合にかかるコストを高速に求められればよい。これはO(1)で求めることができる。
具体的には、下の図(これは入力例2のi=2の場合)を見るといい。右向きが反時計回りの方向として、i=2個方向を変えないで進み続けると、反時計周りの回転で燃やすのは2個(方向転換しない分を増やすと4個)。このときに、方向転換した後は戻ってくるので累積和の2倍の距離を進むことになる。これは左向き(時計回り)についても同様。

ただし、最後の木を燃やした後は戻ってくる必要は無いので、その分だけ最後に累積和から引く必要があるのに注意

int main(){
    ll L,n; cin >> L >> n;
    vector<ll> x(n); rep(i,n) cin >> x[i];

    ll ans = 0;
    rep(loop,2){
        vector<ll> rx(n);
        rep(i,n) rx[i] = L - x[n-1-i];
        vector<ll> sx(n+1,0),srx(n+1,0);
        for(int i=0;i<n;i++) sx[i+1] = sx[i] + x[i];        // sx[i] = x[0] + ... + x[i-1]
        for(int i=0;i<n;i++) srx[i+1] = srx[i] + rx[i];     // srx[i] = rx[0] + ... + rx[i-1]


        for(int i=0;i<n;i++){   // 反時計周りにi個の木を燃やし,燃やした後に方向を逆転しない
            const int r = (n-i+1)/2;
            const int l = n - i - r;

            ll cur = 2*(sx[i+r] - sx[i]);
            cur += 2*srx[l];

            if(l != r){ // 最後にr
                cur -= x[i+r-1];
            }else{      // 最後にl
                cur -= rx[l-1];
            }

            ans = max(ans,cur);
        }

        // 2回目は初手時計回り確定の処理をするが,座標を反転していけば同一処理を使いまわせる
        swap(x,rx);
    }
    cout << ans << endl;
}