CSAcademy Round #67 : E. Hamming Distances

CSAは最近レート落ち続けてたので、久々にまともな順位で良かった。
https://csacademy.com/contest/round-67/task/hamming-distances/

問題

2進数表記でM bitの整数がN個順に与えられる。
新しい整数に対し、それまでに登場した整数に対し2進数表記でのハミング距離が0～Mの物がそれぞれ何個ずつあるか答えよ。

解法

要素を総当たりするとO(N^2)だし、値の種類が2^M通りしかないことを用いてもO(N*2^M)かかるのでこのままではTLEする。

ここでは、値の更新と参照のために計算を半々にすることで、O(N*2^(M/2)*M)程度にすることを考える。
要素を登場するたびに、以下のM*2^M要素のbucketに追加することを考えよう。
B(a,b,c) := それまで登場した要素xのうち、上位(M/2)bitがaで、下位(M/2)bitがbとのハミング距離がcであるものの数
つまり、下位(M/2)bitは要素を追加する段階で全通りチェックしておいてハミング距離を計算してしまい、後の数え上げでは上位(M/2)bitだけ総当たりしよう。

int N,M;
int A[1<<8][1<<8][24];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) {
		int cnt[17]={};
		cin>>x;
		int top=(x>>8)<<8;
		for(j=0;j<1<<M;j+=1<<8) {
			int add=__builtin_popcount(j^top);
			FOR(y,17) cnt[y+add]+=A[j>>8][x&255][y];
		}
		
		FOR(j,256) {
			int add=__builtin_popcount((j^x)&255);
			A[x>>8][j][add]++;
		}
		FOR(x,M+1) _P("%d%c",cnt[x],(x==M)?'\n':' ');
	}
}

まとめ

SegTreeが参照と更新に手間を振り分けるデータ構造だけど、今回もその認識を持って取り組むとわかりやすいかも。