AtCoder Beginner Contest 031 C - 数列ゲーム

C - 数列ゲーム

解法

$N \le 50$と小さい。やるだけ。

実装

pythonでもよかったかも。

#include <iostream>
#include <vector>
#include <climits>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define repeat_from(i,m,n) for (int i = (m); (i) < (n); ++(i))
using namespace std;
int main() {
    int n; cin >> n;
    vector<int> a(n); repeat (i,n) cin >> a[i];
    pair<int,int> result = { INT_MIN, INT_MIN }; // (first player, second player)
    repeat (i,n) {
        int fst_best = INT_MIN;
        int snd_best = INT_MIN;
        repeat (j,n) if (i != j) {
            int l = min(i,j); // [l, r)
            int r = max(i,j) + 1;
            int fst = 0;
            int snd = 0;
            repeat_from (k,l,r) {
                (((k-l) % 2) ? snd : fst) += a[k];
            }
            if (snd_best < snd) {
                fst_best = fst;
                snd_best = snd;
            }
        }
        result = max(result, make_pair(fst_best, snd_best));
    }
    cout << result.first << endl;
    return 0;
}