Hatena::Grouptopcoder

zerokugi's contest memo

2014-10-20ACM-ICPC 2014 Asia Tokyo Regional I: Sweet War

I: Sweet War

問題

美味しさ  r_i と栄養価  s_i をパラメータに持つチョコレートがN個並んでいる

AliceとBriannaは先頭のチョコから交互に取っていくが,エネルギーを1以上持っている場合に限りパスすることができる

初めAliceとBriannaのエネルギーはA, Bであり,チョコを食べるとそのチョコが持つ栄養価の値だけエネルギーが増加する

AliceとBriannaはそれぞれ自分が食べたチョコのおいしさの総和を最大化したい.

二人が最適に行動した時のそれぞれが食べたチョコの美味しさの総和を求めよ

  •  1 < N < 150
  •  0 < A, B, r_i < 10^9
  •  0 < s_i
  •  \sum s_i < 150
解法

AとBが持つエネルギーは差だけ見て以下のように考えればよい

  • 自分のエネルギーが相手のエネルギーよりも同じか少ないならパス不可能(相手もパスをし続けて結局自分が食べることになるため)

こうすると2連続でパスが起きることがなくなる

これを使って貪欲に書くと以下のようなコードになる

int n, A, B;
ll r[200], s[200];
ll sum[200];

// i個目のチョコが先頭にあり
// playerのターンで
// playerの栄養価が相手よりも nut 多い時
// playerが取得できるi個目以降のチョコのおいしさの総和の最大値を返す
int dfs(int player, int i, ll nut){
	if(i == n) return 0;

	// eat
	int res = s[i] + sum[n] - sum[i+1] - dfs(!player, i+1, -(nut + r[i]));

	// pass
	if(nut > 0) res = max(res, dfs(player, i+1, (nut - r[i] - 1)));
	return res;
}

main(){
	ios::sync_with_stdio(false);
	cin >> n >> A >> B;
	REP(i, n){
		cin >> r[i] >> s[i];
		sum[i+1] = sum[i] + s[i];
	}
	int res = dfs(0, 0, A-B);
	cout << res << " " << sum[n] - res << endl;
	return 0;
}


このコードは O(2^n) かかるためTLEするのでこれをメモ化することを考える

単純に考えると memo[player][i][nut] というメモ化が考えられるが,

nutが -75*10^9~75*10^9 ぐらいまで値の範囲を持つのでメモ化できない

しかし,この関数の返り値は0~150までの値のみを取り,player, i を固定するとnutに比例して(広義)単調増加するため,

各player, iに対して返り値が変化する nut の値だけ調べておけば全てのnutに対して正しい値を返すことができる

なので最初に二分探索で変化点を求めておくことでメモ化を実現することができる

以下コード

const ll INF = 1ll<<40;
int n, A, B;
ll r[200], s[200];
ll sum[200];

int solve(int player, int i, ll nut);

// i個目のチョコが先頭にあり
// playerのターンで
// playerの栄養価が相手よりも nut 多い時
// i個目以降のチョコのplayerが取得できるおいしさの総和の最大値を返す
int dfs(int player, int i, ll nut){
	if(i == n) return 0;
	int res = s[i] + sum[n] - sum[i+1] - solve(!player, i+1, -(nut + r[i]));
	if(nut > 0) res = max(res, solve(player, i+1, (nut - r[i] - 1)));
	return res;
}

map<ll, int> memo[2][200];

void fillTable(int player, int i){
	map<ll, int> &tar = memo[player][i];
	int low = tar[-INF] = dfs(player, i, -INF/2);
	int hi = tar[INF] = dfs(player, i, INF/2)+1;
	for(int j=low+1;j<hi;j++){
		ll l=-INF, r = INF;
		while(l<r-1){
			ll med = (l+r)/2;
			if(dfs(player, i, med) < j) l = med;
			else r = med;
		}
		j = tar[r] = dfs(player, i, r);
	}
}

int solve(int player, int i, ll nut){
	if(i == n) return 0;
	if(memo[player][i].empty()) fillTable(player, i);
	auto it = (memo[player][i].upper_bound(nut));
	return (--it)->second;
}

main(){
	ios::sync_with_stdio(false);
	cin >> n >> A >> B;
	REP(i, n){
		cin >> r[i] >> s[i];
		sum[i+1] = sum[i] + s[i];
	}
	int res = solve(0, 0, A-B);
	cout << res << " " << sum[n] - res << endl;
	return 0;
}

本番中、最初はおいしさの総和を固定した時の最小の栄養価の差分を求めるDPを考えてたけど混乱してまとまらず残り40分程度でこのアプローチを思いつく.

残り15分でHが絶望的だったので交代し実装を始めるも間に合わずに終了という悔しい結果に.

戦略次第では通せてた可能性もあったのでなかなか悔しい