CODE FESTIVAL 2016 Grand Final(Parallel) C - Cheating Nim(500)

概要

数列が各山の石の数を表す山ニムを行う。
後手があらかじめ各山から多くとも1つの石を除いてよいとするとき、後手必勝となるために除く最小の石の個数を出力せよ。
また、どのように石を除いても後手必勝とならないときは、-1を出力せよ。

制約

方針

山ニムは各山の石の個数のXORが0であれば後手必勝であり、そのようになるような石の除き方を考える。
のすべてでXORをとった数値をとする。

ある山から石を取り除くことは、下記の操作を行うことに等しい。

• （ある整数について）「下位ビットがすべて1である数」ととでXORをとる

「下位ビットがすべて1である数」は、 XOR であり各ごとに定まる。
よって、の上位ビットから順番に見てゆき、ビットが1であれば、
「XORをとってそのビットを0にできる数」ととでXORをとってゆく。

感想

下記ブログを参考にしました。
wk1080id.hatenablog.com

解答

Submission #3929799 - CODE FESTIVAL 2016 Grand Final(Parallel)

#include <bits/stdc++.h>
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
int dig(int x){
	for(int i = 31; i >= 0; i--){
		if((x >> i) & 1) return i;
	}
}
 
int mask(int d){
	return (1 << (d+1)) - 1;
}
 
void print(int x){
	for(int i = 10; i >= 0; i--){
		cout << ((x & (1 << i)) >> i);
	}
	cout << endl;
}
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int n;
	cin >> n;
 
	int a[n];
	rep(i, n) cin >> a[i];
 
	int x = 0;
	rep(i, n) x ^= a[i];
	// print(x);
 
	if(x == 0){
		cout << 0 << endl;
		return 0;
	}
 
	int b[n];
	rep(i, n) b[i] = dig(a[i] ^ (a[i]-1));
	bool u[n] = {};
 
	int ans = 0;
	for(int i = 31; i >= 0; i--){
		if(x & (1 << i)){
			bool updated = false;
			rep(j, n){
				if(!u[j] && b[j] == i){
					updated = true;
					x ^= a[j] ^ (a[j]-1);
					u[j] = true;
					ans++;
					break;
				}
			}
			if(!updated){
				cout << -1 << endl;
				return 0;
			}
		}
 
	}
	if(x == 0){
		cout << ans << endl;
	}else{
		cout << -1 << endl;
	}
 
}