Codeforces #228 Div1. C. Fox and Card Game

本番ちらっと頭に浮かんだけど、自信がなくて別解に挑んで撃沈してしまった…。
http://codeforces.com/contest/388/problem/C

問題

N個のカードの山がある。
i番目の山にはS[i]枚のカードが積んであり、j枚目のスコアはC[i][j]である。

ここで２人で交互にカードを取るゲームを行う。
２人は、残されたカードのうち先手は任意の山の先頭、後手は山の末尾のカードを１枚取り、自分のスコアに加算できる。
両者が最適手を取った場合、両者の最終スコアを答えよ。

解法

S[i]が偶数の場合、先手が前半半分のカード、後手が後半半分のカードを取る。
S[i]が奇数の場合、真ん中のカードを残して、先手が前半半分、後手が後半半分を取る。

S[i]が奇数があると真ん中のカードが全体で何枚か余るので、降順ソートして先手・後手…の順に割り振ればよい。

上記手順が最適であることを示すには、互いに最適手を取ると片方が半分を超えてとることがないことを示せばよい。

例えば山1が６枚中先頭４枚が良いカードで、逆に山2が６枚中末尾４枚が良いカードだとする。
この場合は先手は山１、後手は山２をガンガンとればよさそうに見えるが、実際はそうはならない。
なぜなら、山１の４枚目が良いカードなら後手が山１を積極的にとれば先手より先に取れるし、山２には逆の状態が成り立つ。

よって、互いに真ん中以降のカードをとっても相手に先んじれないため、結果的に真ん中までを取り合うことになる。
奇数枚の山の真ん中に関しては、交互に取るチャンスが巡ってくるので降順に割り振ればよい。

int N;
int S[101];
vector<int> V;

void solve() {
	int f,i,j,k,l,x,y;
	int sa=0,sb=0;
	
	cin>>N;
	FOR(i,N) {
		cin>>S[i];
		FOR(j,S[i]) {
			cin>>x;
			if(j<S[i]/2) sa+=x;
			else if(S[i]%2 && j==S[i]/2) V.push_back(x);
			else sb+=x;
		}
	}
	
	sort(V.begin(),V.end());
	reverse(V.begin(),V.end());
	FOR(i,V.size()) {
		if(i%2) sb+=V[i];
		else sa+=V[i];
	}
	_P("%d %d\n",sa,sb);
}

まとめ

Nがもっと多ければ変な探索を早々にあきらめたかもしれないが、Nが変に小さかったのでダメ解法でpretestが通ってしまった…。
まぁN*S[i]を取ると1万になるので、これ以上早々増やせないのだろうけど。