TopCoder SRM 709 Div1 Easy Xscoregame

Easyを落としたが、Mediumで非想定解と思われる解が通ってレート増だった。
https://community.topcoder.com/stat?c=problem_statement&pm=14533

問題

N要素の整数列A[i]がある。
初期値0である変数Xに対し、A[i]を順にX := X + (X ^ A[i])の式に当てはめXを変化させていくことを考える。
Aの順番を任意に並び替えられるとき、処理後のXの最大値を求めよ。

解法

BitDPで処理を行っていく。
その際、A[i]は50以下のため、2進数でいうとA[i]の値は32の桁までしか影響しない。

よって、下6bitの値で分類して以下の値を更新して行くとよい。
S(bitmask,d) := A中bitmaskに示す要素を利用済みで、Xの下6bitがdであるようなXの最大値。

int S[1<<15][64];

class Xscoregame {
	public:
	int getscore(vector <int> A) {
		int N=A.size();
		int i,j;
		
		MINUS(S);
		S[0][0]=0;
		
		int mask,ret=0;
		for(int mask=0;mask<(1<<N);mask++) {
			FOR(j,64) if(S[mask][j]>=0) {
				ret = max(ret,S[mask][j]);
				
				FOR(i,N) if((mask&(1<<i))==0) {
					int mask2=mask|(1<<i);
					int nv=S[mask][j]+(S[mask][j]^A[i]);
					
					S[mask2][nv&63]=max(S[mask2][nv&63],nv);
				}
			}
		}
		return ret;
	}
}

まとめ

これ本番全然思いつかなくてダメだった。
嘘解法でやっぱり落ちてしまった。