読者です 読者をやめる 読者になる 読者になる

kmjp's blog

競技プログラミング参加記です

Codeforces #228 Div1. C. Fox and Card Game

Codeforces

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

問題

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

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

解法

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

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

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

例えば山1が6枚中先頭4枚が良いカードで、逆に山2が6枚中末尾4枚が良いカードだとする。
この場合は先手は山1、後手は山2をガンガンとればよさそうに見えるが、実際はそうはならない。
なぜなら、山1の4枚目が良いカードなら後手が山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万になるので、これ以上早々増やせないのだろうけど。

広告を非表示にする