ACM-ICPC 2014 アジア地区東京大会 I

ACM-ICPC 2014 アジア地区東京大会

I: Sweet War

問題
カカオ帝国の女帝アリスとココア公国の王妃ブリアンナは友人で、二人ともチョコレートが大好き。

以下意訳
スタックにチョコレートが幾つか入っている。各チョコレートは個別に栄養価r[i]と幸福度s[i]が決まっている。
AliceとBriannaはターン制のゲームを行う。二人はそれぞれ体力が有る(初期値それぞれA,B)。次の2つの行動から選んで行動する。
Pass 体力が1以上ならば選択できる。体力が1減り、相手のターンになる。
Eat スタックのトップのチョコレートiを食べ、食べた人は体力がr[i]増え、幸福度がs[i]増え、相手のターンになる。

ゲームはスタックが空になると終了。二人は幸福度を最大にするように最適に行動する。ゲーム終了時の二人の幸福度を求めよ。

チョコレートの数N<=150
空腹度の初期値0<=A,B<=10e9
0<=r[i]<=10e9
0<=s[i]
sum s[i]<=150

解法
DPであることが予想できるが体力はDPのキーにできない。幸福度をキーにすることを考える。

二人が連続してパスをすることはゲームとして何も変わらない（と思う）。体力が相手より多い時には先頭のチョコレートを相手に押し付けることができる。

体力の差(A-B)だけを考える。
FA[i][j] := Aliceのターン、スタックのtopがiのとき、残りのゲームでAliceが幸福度j以上を取るために最低限必要な体力の差
FB[i][j] := Briannaのターン、スタックのtopがiのとき、残りのゲームでAliceが幸福度j以上取るために必要最低限の体力の差

DPの式を頑張る。
Aliceはなるべく体力差を小さくしたい。
Briannaはなるべく体力差を大きくしたい。
Passするには体力が相手より大きくなければならない。
FA[i][j],FB[i][j]はjについて単調増加にする。

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;
#define REP(i, n) for (int i=0; i<int(n); i++)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)

template<class T> inline T &amin(T &a, const T &b) { if (a>b) a=b; return a; }
template<class T> inline T &amax(T &a, const T &b) { if (a<b) a=b; return a; }
typedef long long LL;

const LL INF = 1LL<<60;

int N;
LL A, B;
LL r[155];
int s[155];

LL FA[155][155]; 
LL FB[155][155];

int main() {
    scanf("%d%lld%lld", &N, &A, &B);
    REP (i, N) scanf("%lld%d", r+i, s+i);

    int sum = 0;
    REP (i, N) sum += s[i];


    REP (i, 155) REP (j, 155) {
        FA[i][j] = INF;
        FB[i][j] = INF;
    }
    // no chocolate
    FA[N][0] = -INF; 
    FB[N][0] = -INF;
    
    LL tmp;
    for (int i=N; i--;) {

	// Alice's turn
	for (int j=sum; j>=0; j--) {
	    tmp = INF;
	    amin(tmp, FA[i][j+1]); // monotone
	    if (j >= s[i]) amin(tmp, FB[i+1][j-s[i]]-r[i]); // Eat
	    amin(tmp, max(1LL, FA[i+1][j]+1+r[i])); // Pass
	    FA[i][j] = tmp;
	}

	// Brianna's turn
	for (int j=0; j<=sum; j++) {
	    tmp = -INF;
	    if (j) amax(tmp, FB[i][j-1]); // monotone
	    amax(tmp, FA[i+1][j]+r[i]); // Eat
	    if (j >= s[i]) amax(tmp, min(1LL, FB[i+1][j-s[i]]-r[i]-1)); // Pass
	    FB[i][j] = tmp;
        }
    }


    int ans = 0;
    REP (i, sum+1) if (FA[0][i] <= A-B) ans = i;
    printf("%d %d\n", ans, sum-ans);


    return 0;
}