Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2011-05-08Google Code Jam 2011 Qual Round

Google Code Jam 2011 Qual Round C Candy Splitting

| 13:14 | Google Code Jam 2011 Qual Round C Candy Splitting - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam 2011 Qual Round C Candy Splitting - SRM diary(Sigmar) Google Code Jam 2011 Qual Round C Candy Splitting - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

パトリックの計算方法はxorに等しい

ある2つの集合に分けたとき、各集合のxorがx1、x2となるとすると、xorの性質よりx1=x2のときx1^x2=0

従ってNOとなる条件は、全てのキャンディをxorして0にならないこと

また、NOとならない場合x1^x2=0となることから、どのような分け方をしてもx1=x2となる

なのでパトリックには一番価値の低いキャンディを1つあげれば良い


ソースコード

入出力処理は省略

NOの場合は-1を返す

int solve(int N, vector <int> C) {
	int res=0;
	
	int cur=0;
	for(int i=0; i<N; i++) cur^=C[i];
	if(cur!=0) return -1;

	sort(C.begin(), C.end(), greater <int>());
	res=accumulate(C.begin(), C.end()-1, 0);
	return res;
}
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20110508