TopCoder SRM 699 Div1 Easy OthersXor

EasyもMediumも通ったけど、簡単目な上あまり早くなかったのでレートは余り上がらなかった。
https://community.topcoder.com/stat?c=problem_statement&pm=14396

問題

ある整数列V[i]が存在するとする。
X[i]は、VからV[i]を除いたもののxorを取った値とする。
ただし一部のX[i]は未定であるとする。

Xが与えられたとき、そのようなXを満たす元のVが存在するならば、そのうち総和の最小値を求めよ。

解法

X[i]はV[i]の各ビットのxorで決まる。
以下、X,Vは2進数で1桁、すなわち0,1のどちらかのみを取ることとする。
他の桁についても、各桁個別に考え、最後に足し合わせればよい。

SをVの各要素のxorを取った値とすると、X[i]^V[i]=X[j]^V[j]=Sなので、X[i]=X[j]ならV[i]=V[j]である。
Xのうち確定済みのものについて、0であるものがn0個、1であるものがn1個あるとする。
この場合、X[i]=0であるn0個側か、X[i]=1であるn1個側のどちらかが1であり、もう片方が0である。

下記それぞれを満たす可能性があるなら、そのうち最小値が解。
いずれも状態を満たせない場合、解無し。未定の数が1個以上あるなら、解が無いことはない。

• n1が偶数なら、n1個の要素がX[i]=1でありうる
• n0が奇数なら、n0個の要素がX[i]=1でありうる
• n1が奇数なら、未定の数が1個以上あれば、未定の数1個を含めて(n1+1)個の要素がX[i]=1でありうる
• n0が偶数なら、未定の数が1個以上あれば、未定の数1個を含めて(n0+1)個の要素がX[i]=1でありうる

class OthersXor {
	public:
	long long minSum(vector <int> X) {
		
		ll ret=0;
		int i;
		FOR(i,30) {
			ll n[2]={};
			int mi=0;
			ll num=1010;
			FORR(x,X) {
				if(x==-1) mi++;
				else n[(x>>i)&1]++;
			}
			
			if(n[1]%2==0) num=min(num,n[1]);
			if(n[0]%2==1) num=min(num,n[0]);
			if(mi) {
				if(n[1]%2==1) num=min(num,n[1]+1);
				if(n[0]%2==0) num=min(num,n[0]+1);
			}
			if(num>1000) return -1;
			ret += num<<i;
		}
		return ret;
	}
}

まとめ

本番はだいぶ無駄が多いコードを書いてしまい時間を掛けてしまったけど、まぁミスするよりはマシだね。