AtCoder Beginner Contest 031 C 数列ゲーム

芝浦競プロ検討会の復習 (https://not-522.appspot.com/contest/6468297472081920)

問題概要

長さ の数列 がある。高橋君と青木君はそのうち2つの整数を選んで丸をつけ、その間にある整数以外は削除する。残った数列を と置き、 の奇数要素の総和を高橋君の得点、偶数要素の総和を青木君の得点とする。青木君が高橋君の丸の付け方を知っているとき、高橋君が得られる得点として考えられる最大値を求めよ。

考察

今回は数列の大きさの制約が と小さいので、高橋君の丸の付け方を全て試すことができ、高橋君が取得できる得点を全探索することによって答えを求めることができます。

次に高橋君が に丸を付けたときの点数の求め方を考えます。これも数列の大きさの制約が小さいため、青木君の丸の付け方を全て試すことで、高橋君が に丸を付けたときの青木君の得点の最大値を求めることができます。問題文から青木君は高橋君が丸をつけた後に自分の得点が最大になるように丸をつけられます。この条件から、青木君の得点が最大になる場合の高橋君の得点が に丸を付けたときの点数になります。

高橋君の丸の付け方とその時の高橋君の点数の求め方の計算量は で収まるため、この問題を解くことができました。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <functional>
#include <queue>
#include <string>
#include <cstring>
#include <numeric>
#include <cstdlib>
#include <cmath>
#include <map>
#include <unordered_map>
#include <set>
using namespace std;

typedef long long ll;

#define INF 10e17
#define rep(i,n) for(long long i=0; i<n; i++)
#define repr(i,n,m) for(long long i=m; i<n; i++)
#define END cout << endl
#define MOD 1000000007
#define pb push_back
#define sorti(x) sort(x.begin(), x.end())
#define sortd(x) sort(x.begin(), x.end(), std::greater<long long>())
#define debug(x) std::cerr << (x) << std::endl;
#define roll(x) for (auto&& itr : x) { debug(itr); }

template <class T> inline void chmax(T &ans, T t) { if (t > ans) ans = t;}
template <class T> inline void chmin(T &ans, T t) { if (t < ans) ans = t;}

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

    int n;
    cin >> n;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];

    int ans = -10000;

    rep(i, n) {
        pair<int, int> aokiMax = make_pair(-10000, 100);
        int tMax = -10000;
        rep(j, n) {
            if (i == j) continue;

            auto mark = i;
            int takahashi = 0;
            int aoki = 0;

            if (j > mark) {
                for (int k = mark, cnt = 1; k <= j; ++k, ++cnt) {
                    if (cnt % 2 == 0)
                        aoki += a[k];
                    else
                        takahashi += a[k];
                }
            } else {
                for (int k = j, cnt = 1; k <= mark; ++k, ++cnt) {
                    if (cnt % 2 == 0)
                        aoki += a[k];
                    else
                        takahashi += a[k];
                }
            }

            if (aoki > aokiMax.first) {
                aokiMax = make_pair(aoki, j);
                tMax = takahashi;
            }
        }
        chmax(ans, tMax);
    }

    cout << ans << endl;
}

提出コード atcoder.jp