topcoder

kojingharangの日記

2011-05-08

C. Candy Splitting

22:59 |

正の整数値が書きこまれたアメが袋にたくさん入ってる。（なんだそのアメ！！）
Seanがアメを２つのグループに分ける。
Patrickが２つのグループそれぞれの合計を算出する。合計が等しくないとPatrickは泣き出す。
Patrick が泣かなかった場合 Seanは自分がもらうグループを選ぶことができる。
Patrick は２進数の加算の繰り上げができないので排他的論理和を計算してしまう。
Seanははちゃんと加算できるので、自分で選ぶグループの合計が最大になるように２グループに分けたい。
Patrick が泣かないようにできるか、もしそうならSeanが貰える合計の最大値を求める。

Patrick が泣かない←→すべてのアメのXOR==0 でとりあえず判断できそう。
で、分け方は 2^(アメの数) 通りある。largeではアメの数が最大1000なので全通り試すみたいなのは破綻するな
なんかうまい方法があるんだろう
（う〜〜〜〜ん.......）
（う〜〜〜〜ん.......）
（う〜〜〜〜ん.......）
最大にしたいということなので、強欲に「１番小さいのとそれ以外」で分けたらどうだ
XORなのでなんかうまくいきそうな気がする
「全XORが0の場合、「任意の１つとその他」でグループ分けするとかならずXOR値が等しくなる」を証明したいでござる
全XOR==0 → 任意の２グループのXOR==0 ということなので、「１番小さいのとそれ以外」で分けても成り立つ。証明だん。

なので、全アメの合計から一番小さいやつを引いたのが答え。
ソートしたけど、最小値を求めるだけなら不要ですね。。

int main()
{
	int T;
	cin>>T;
	//cout<<T<<endl;
	REP(t, T)
	{
		int n;
		cin>>n;
		VI c(n);
		int x=0;
		int sum=0;
		REP(i, n)
		{
			cin>>c[i];
			x ^= c[i];
			sum+=c[i];
		}
		SORT(c);
		sum -= c[0];
		//cout<<c<<endl;
		if(x==0)
		{
			cout<<"Case #"<<t+1<<": "<<sum<<endl;
		}
		else
		{
			cout<<"Case #"<<t+1<<": NO"<<endl;
		}
	}
	return 0;
}