単純な全探索で解ける！　累積和で高速化したり DP したりしても OK

問題へのリンク

問題概要

$2 \times N$ のマス目があり、上から $i$ 行目、左から $j$ 列目のマスをマス $(i, j)$ と表すことにする。マス $(i,j)$ には $A_{i,j}$ 個のアメが置かれている。

あなたははじめ、左上のマス $(1, 1)$ にいる。右方向または下方向への移動を繰り返し、右下のマス $(2,N)$ に移動したい。

移動中に拾うアメの個数の最大値を求めよ。

制約

$1 \le N \le 100$

解法

0-indexed で考える。つまり、左上のマスを $(0, 0)$ 、右下のマスを $(1, N-1)$ と考えることにする。

経路はすべからく、次図のように、

ある地点まで右に移動する
下に移動する
再び右に移動する

というようになる。

「下に移動するのが何列目か」で場合分けすればよい。 $i (= 0, 1, \dots, N-1)$ 列目で下に移動するとき、拾うアメの個数は

$A_{0, 0} + A_{0, 1} + \dots + A_{0, i}$
$A_{1, i} + A_{1, i+1} + \dots + A_{1, N-1}$

の総和となる。各 $i$ に対してこの総和を求めて、その最大値を求めればよい。

計算量は、 $i$ についての場合分けが $O(N)$ 通りあり、それぞれについて総和計算に $O(N)$ を要するので、全体で $O(N^{2})$ となる。

コード

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

int main() {
    int N;
    cin >> N;
    vector<vector<long long>> A(2, vector<long long>(N));
    for (int i = 0; i < 2; ++i) 
        for (int j = 0; j < N; ++j)
            cin >> A[i][j];

    long long res = 0;
    for (int i = 0; i < N; ++i) {
        // i 列目で下に移動する場合の総和を求める
        long long sum = 0;
        for (int j = 0; j <= i; ++j) sum += A[0][j];
        for (int j = i; j < N; ++j) sum += A[1][j];

        // 最大値を更新する
        res = max(res, sum);
    }
    cout << res << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 087 C - Candies (ARC 090 C) (灰色, 300 点)

問題概要

制約

解法

コード