No.999 てん vs. ほむ

Quiz

https://yukicoder.me/problems/no/999

公式解説

https://yukicoder.me/problems/no/999/editorial

私の解説

• 累積和を使わなかったので書いておく
• ほむちゃんが左から攻める領域と、右から攻める領域は2つは左右に分割されるので、切れ目を全探索。各切れ目ごとに得点を求めてmaxをとっていけばいい

例：サンプル３

code 抜粋

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N; 
    cin>>N;

    VI A(2*N);
    rep(i, 2*N) cin >> A[i];

    // 左から取った場合のほむちゃんのスコア
    VI V;
    for(int i=0; i<2*N; i+=2){
      ll a = A[i];
      ll b = A[i+1];
      V.push_back(a-b);
    }

    ll sum = SUM(V);
    ll ma = sum;

    for(int i=N-1; i>=0; i--){
      // i番目を右から取った場合に変更する
      sum -= 2*V[i];
      chmax(ma, sum);
    }
    p(ma);
    
    return 0;
}

プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～