【競プロ】1日1AC : ABC87 C問題

2日ぶりです。今日の問題はこちら。

提出コードと考え方

制約が緩いのでループを回してゴリゴリ最大値を見つけることもできますが、累積和というものを利用しましょう。以下では累積和を知らない前提で書きます。

行は「 \(0\) 行目、\(1\) 行目」で表し、 \(i\) 行目のアメの個数の列は \(A_{i,0},A_{i,1},\cdots ,A_{i,N-1}\) で与えられるとします。また、\(A_{i,j}\) を単に \(j\) 番目と呼び、「 \(0\) 番目から \(j\) 番目」を「 \([0,j]\) や\([0,j+1)\) 」のように表します。
\(S_{i,j}\) を「 \(i\) 行目の \([0,j)\) の和」（ ただし、\(S_{i,0}=0\) ）とします。このとき以下が成り立ちます。
\[S_{i,j+1}=S_{i,j}+A_{i,j}\]
\(j\) についてループを回すと、\(0\) 番目から任意の番号までのアメの総和が配列に記憶されます。

こうすると便利なのは、「 \([j,k]\) の和が求められる」ということです。実際、この値は 「 \(S_{i,k+1}-S_{i,j}\) 」 で求められます。【「 \([0,k]=[0,k+1)\) の和 」 \(-\) 「 \([0,k-1]=[0,k)\) の和」】と考えるとわかりやすいと思います。

問題で考えるべきは【「 \(0\) 行目の \([0,j]\) の和」 \(+\) 「 \(1\) 行目の \([j,N-1]\) の和」】、すなわち
\[S_{0,j+1}+S_{1,N}-S_{1,j}\]
です。
ループを回してこの最大値を探しましょう。

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N;
    cin >> N;
    vector<vector<int>> A(2,vector<int>(N));
    for(int i = 0;i < 2;i++){
        for(int j = 0;j < N;j++){
            cin >> A[i][j];
        }
    }
    vector<vector<int>> S(2,vector<int>(N+1,0));
    for(int j = 0;j < N;j++){
        S[0][j+1] = S[0][j] + A[0][j];
        S[1][j+1] = S[1][j] + A[1][j];
    }
    int ans = 0;
    for(int j = 0;j < N;j++){
        ans = max(ans,S[0][j+1] + S[1][N] - S[1][j]);
    }
    cout << ans << endl;
    return 0;
}