google code jam 2011 Qualification Round C Candy Splitting

program gcj

問題

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

方針

これは、方針を考えるのに苦労した。けど、方針が分かればコーディングは一瞬。前の2問とは逆のパターン。
求められていることを、抽象的に述べると、次のとおりになる。

  • 数列 a[i] (i = 1, ..., m) を空でない2つの数列 b[i] (i = 1, ..., n), c[i] (i = 1, ..., l)に分ける。
  • 但し、b[1] ^ ... ^ b[n] = c[1] ^ ... ^ c[l] を満たさないと駄目。
  • さらに、このような分割の中で、(b[1] + ... + b[n]) - (c[1] + ... + c[l])が最大になるものを探せ。

ここで、^は、ビット毎のXOR演算である。問題のサイズ的に、全探索は無理。
キモは、

x ^ y = 0 iff. x = y

が成り立つことである。これに気がつくと、

a[1] ^ ... ^ a[m] = 0

なら、任意の分割について、

(b[1] ^ ... ^ b[n]) ^ (c[1] ^ ... ^ c[l]) = 0

が成り立つことから

b[1] ^ ... ^ b[n] = c[1] ^ ... ^ c[l]

となることが分かる。従って、a[i]の最小値を分割の片方として、残りを他方とする分割が求めるものである。但し、

a[1] ^ ... ^ a[m] != 0

の場合には、条件を満たす分割は不可能である。
取り組み始めて、1時間くらい頭の中で考えていたけど、さっぱり分からなかった。で、数式に倒していじりはじめたら、割とすんなりと分かった。

回答

#include <iostream>
#include <climits>
#include <iomanip>


using namespace std;


void solve(int x){
  int n;
  cin >> n;

  long sum = 0;
  long minval = 1000000;
  long buf;
  long check = 0;
  for(int i = 0; i < n; i++){
    cin >> buf;
    sum += buf;
    minval = min(minval, buf);
    check ^= buf;
  }
  sum -= minval;

  if(check == 0){
    cout << "Case #" << x << ": " << sum << endl;
  }
  else{
    cout << "Case #" << x << ": " << "NO" << endl;
  }
}

int main(int argc, char *argv[]){
  int n;
  cin >> n;

  for(int i = 0; i < n; ++i){
    solve(i + 1);
  }

  return 0;
}