GCJ2011 Qualification Round C Candy Splitting

http://code.google.com/codejam/contest/dashboard?c=975485#s=p2

問題

• 問題文の設定にいろいろツッコミをしたくなるが，我慢我慢
• いや，飴を分ける前に，普通の足し算はわからないのにこんな不思議なビット演算をしてしまうパトリックに計算の仕方を教えてあげた方が将来的にはいいんじゃないか？というのは置いといて，
• 与えられた飴の列をパトリックが泣かないように，パトリックの計算法で2つの山の合計が等しくなるようにできるか．その場合の最大値はいくらか？

プログラム

import java.util.*;
import java.io.*;

public class Qualifer_03_2011 {
	public void solve() throws Exception {
		Scanner sc = new Scanner(new FileReader("./input/C-large-practice.in"));
		PrintWriter pw = new PrintWriter(new FileWriter("./output/Q03_2011output.txt"));

		int caseCnt = sc.nextInt();

		for (int caseNum = 0; caseNum < caseCnt; caseNum++) {
			pw.print("Case #" + (caseNum + 1) + ": ");
			int N = sc.nextInt();
			int xor = 0, min = Integer.MAX_VALUE, sum = 0;
			for (int i=0; i < N; i++) {
				int x = sc.nextInt();
				xor ^= x;
				sum += x;
				min = Math.min(min, x);
			}
			pw.println(xor == 0 ? sum - min : "NO");
		}

		pw.flush();
		pw.close();
		sc.close();
	}

	public static void main(String[] args) throws Exception {
		new Qualifer_03_2011().solve();
	}
}

まったくもって方針が立たなかったんだけど，パトリックの謎の計算法に騙されすぎていて，要は排他的論理和によるパリティチェックをして，0になればOKという話に気付くのに随分時間がかかった．次に最大値については，排他的論理和が0となる集合であるならば，一方の山を最小値のみにして，もう一方を残り全てにすれば良いということに気付けるので，総和から最小値を引けばよいという感じですね．