CS Academy #1 - Unfair Game

問題

https://csacademy.com/contest/archive/#task/unfair_game/

問題概要

個の整数で構成される集合がある。この集合を使ってAlexとBenはゲームを行う。Alexが先手、Benが後手となって交互に自分のターンを行うが、このゲームでは先手と後手ではできる行動が異なる：

• 先手(Alex)は、空ではない部分集合を選び、集合から取り除く。
• 後手(Ben)は、集合から1つの要素を選び、取り除く。

このようなルールで選べる数がなくなるまでゲームを行い、取り除いた要素の値の合計が得点となる。Alexは自分の得点を最大化するために、BenはAlexの得点を最小化するために最適な行動を選択する時、Alexの得られる点数を求めよ。

• 
• 

アイデア

まず、Benの戦略に着いて考えてみると、ターンが回ってくるごとに残っている要素の中で最大のものを選ぶのが最善であることはその次のターンでAlexに取らせたくないものは何かと考えれば自然である。次に、Alexの戦略についても考えてみる。Alexはは先に行動できるので、得点を最大化するなら1番最初に非負のものは全部取ってしまえば良い。残りは負の値をどうするかだが、負の値はできるだけ取りたくない。つまりAlexも負の値は1ターンに1個、絶対値が最小のものをえらんでいくことになる。

つまり、ゲームの流れとしては非負の要素が1個以上ある時には最初に非負の要素をAlexが取り切ってその後は交互に負の値を絶対値が小さい方から交互に取っていくという流れになる。ただ、この時に交互に取っていくということを考慮すると最適になりうるのはAlexが初手で

• 非負の要素全てのみを取る
• 非負の要素全て + 負の値を1つだけ取る

のどちらかが最適ということになる。下が最適になる場合というのは、例えば5, 3, -1, -2, -100のような場合である。

そして、全ての値が負だった時には、1つも取らないということはできないので初手は1つか2つを取るのが最適ということになる。

実装(C++)

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

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

const ll INF=123456789012345LL;

int main()
{
    int n;
    scanf(" %d", &n);
    vector<ll> a(n);
    rep(i,n) scanf(" %lld", &a[i]);

    sort(all(a), greater<ll>());

    //大きい方から選んでいくのが最善

    //負の値は数列a内のどこから始まっているか
    int neg_idx=0;
    while(neg_idx<n && a[neg_idx]>=0) ++neg_idx;

    ll ans = -INF;
    if(neg_idx==0)
    {
        //集合の要素が全て負の時
        //初手は1つか2つ
        ll one=0, two=0;

        one=a[0];
        for(int i=2; i<n; i+=2) one+=a[i];
        ans=max(ans,one);

        if(n>=2)
        {
            two=a[0]+a[1];
            for(int i=3; i<n; i+=2) two+=a[i];
            ans=max(ans,two);
        }
    }
    else
    {
        //非負の要素をすべて選ぶか、負の値を1つだけ選ぶ
        ll x=0, y=0;

        rep(i,neg_idx) x+=a[i];
        for(int i=neg_idx+1; i<n; i+=2) x+=a[i];
        ans=max(ans,x);

        if(neg_idx<n-1)
        {
            rep(i,neg_idx+1) y+=a[i];
            for(int i=neg_idx+2; i<n; i+=2) y+=a[i];
            ans=max(ans,y);
        }
    }

    cout << ans << endl;
    return 0;
}