Codeforces 388(#228 Div1) C. Fox and Card Game

問題

二人がゲームをする。
n個のカードの山があって、i番目の山にはsi枚のカードが積まれていて、上から順にci1, ci2, ..., cisiである。
先手は好きな山を選んで先頭からカードを一枚、後手は好きな山を選んで底からカードを一枚引くというのをカードがなくなるまで繰り返す。


自分が引いたカードの合計が自分の点数で、プレイヤーは自分の点数を最大化したい。
お互いが最善を尽くすとき、先手の点数と後手の点数を出力せよ。

制約条件

n≦100
si≦100
cij≦100

方針

まず全部の山のサイズが偶数だった場合を考えてみる。
この場合、実は、全部si/2枚ずつ取るしかなくなる。


なぜかと言うと、si/2枚より多く取ったほうが先手が有利になる山があったとしたら、
(ゲームの先手+後手の得点は必ずカードの総和となって一定だから)
先手が有利になる=後手が不利になるで、後手はその手を回避しようとしてその山を半分まで取るから。


後手が有利になる山があったとしても先手がsi/2枚取るのでその手は実現しない。
で、結局全部真ん中まで取って終わる。


奇数の山がある場合も基本的に同じで、真ん中よりも向こうを取る手はお互いに絶対実現しないので、
真ん中の取り合いになる。
真ん中の大きい順に先手、後手、先手、後手……と取ってゲームが終了する。

int a[100][100];

int main(){
	int n, first = 0, second = 0;
	vi odd;
	cin >> n;
	
	rep(i, n){
		int k;
		cin >> k;
		rep(j, k) cin >> a[i][j];
		if(k % 2) odd.pb(-a[i][k / 2]);
		rep(j, k / 2){
			first += a[i][j];
			second += a[i][k - 1 - j];
		}
	}
	sort(all(odd));
	rep(i, odd.size()){
		if(i % 2 == 0) first -= odd[i];
		else second -= odd[i];
	}
	
	cout << first << " " << second << endl;
	return 0;
}