CS Academy Unfair Game

リンク : https://csacademy.com/contest/archive/task/unfair_game/

問題概要

AlexとBenがゲームをする。長さNの数列を扱う。Alexは自由に1個以上の数列を取ることができる。Benは1個の数列しか取ることができない。Alexは取った数列の合計を最大化しようとし、BenはAlexが取る数列の合計を最小化するとする。2人が最適な行動をする場合、Alexの取る数列の合計の最大はいくつか。

解説

タイトル通り不公平だと思った。もし、数列がすべて正ならAlexが最初にすべて取ってしまえば最大化になる。そうではない場合を考える。数列の中の最小値は必ず負になる。これはAlexは取りたくない。だから、Benに押し付ける。しかし、押し付けるためにはAlexは2番目の最小値をとる必要がある。このように小さいほうから考えると考えやすい。注意することとして、最小値は必ずBenに取らせるため、Alexの最初の操作で負を含む可能性があること。

LL n,ans,a[110000];

int main() {
    cin >> n;
    rep(i, n) {
        cin >> a[i];
    }
    sort(a, a + n);
    if (a[0] >= 0) {
        rep(i, n)
            ans += a[i];
    }
    else {
        rep(i, n) {
            if (a[i] > 0)ans += a[i];
            else {
                if (i == n-1)ans += a[i];
                else if (i % 2 == 0) {}
                else { ans += a[i]; }
            }
        }
    }
    cout << ans << endl;
    return 0;
}