Google Code Jam 2014 Round 1A : A. Charging Chaos

GCJ R1Aに参加。事情で慣れない環境かつ時間いっぱい挑戦できない状態だったが、何とかA-LargeとB-Largeを通してR1A突破。
https://code.google.com/codejam/contest/2984486/dashboard#s=p0

問題

２進数L桁の数値N個からなる配列S[i]とT[i]を与えられる。
S[i]の各要素に同じ値Aをxorを取り、並べ替えてT[i]を構成できるようなAのうち、最少ビット数を答えよ。

解法

S[0]がT[x]に対応する、と仮定するとA=S[0]^T[x]でAが求められるので、S[i]^Aを並べ替えてTを生成できるか総当たりすればよい。
AのバリエーションがN通り、Tの一致判定がS[i]^AのソートでO(N*logN)なので合わせてO(N^2*logN)で処理できる。

…というのが簡単な解法だが、自分は本番そこまで思い浮かばなかった。
Aを下の桁から0,1を入れて探索し、Aの下p桁まで決まったら、S[i]^Aの下p桁とT[i]の下p桁が一致するかを毎回調べていった。
一見2^L通りAを探索する必要がありそうだが、下p桁判定が0でも1でもうまくいくのは高々logN回なので実際の探索空間はそこまで膨らまない。

以下は本番書いたかなり冗長な探索コード。

int N,L;
ll S[200],T[200],E[200];
int ret=1000;

int okok(ll mask,int cur) {
	ll s2[200];
	ll t2[200];
	int i;
	FOR(i,N) s2[i]=(S[i]^mask)&((1LL<<cur)-1);
	FOR(i,N) t2[i]=T[i]&((1LL<<cur)-1);
	sort(s2,s2+N);
	sort(t2,t2+N);
	FOR(i,N) if(s2[i]!=t2[i]) return 0;
	return 1;
}

void dfs(int cur,ll mask) {
	if(okok(mask,cur)==0) return;
	if(cur==L) {
		ret=min(ret,__builtin_popcountll(mask));
		return;
	}
	if(__builtin_popcount(mask)>ret) return;
	
	dfs(cur+1,mask);
	dfs(cur+1,mask | (1LL<<cur));
}


void solve(int _loop) {
	int f,i,j,k,l,x,y;
	cin>>N>>L;
	string s;
	ZERO(S);
	ZERO(T);
	FOR(i,N) {
		cin>>s;
		FOR(j,L) if(s[j]=='1') S[i] |= 1LL<<j;
	}
	FOR(i,N) {
		cin>>s;
		FOR(j,L) if(s[j]=='1') T[i] |= 1LL<<j;
	}
	sort(S,S+N);
	sort(T,T+N);
	ret=1000;
	dfs(0,0);
	
	if(ret==1000) _P("Case #%d: NOT POSSIBLE\n",_loop);
	else  _P("Case #%d: %d\n",_loop,ret);
}

まとめ

本番探索でも間に合ったからいいけど、これは簡潔な方の解法を思いつきたかった…。