AtCoder ABC #425 (ユニークビジョンプログラミングコンテスト2025 秋) : G - Sum of Min of XOR

なんか途中あまりスムーズではなかった。
https://atcoder.jp/contests/abc425/tasks/abc425_g

問題

整数列Aと正整数Mが与えられる。

を答えよ。

解法

f(A,M,d) := Aの各要素が(1<

• Aの中に(1<<(d-1))のbitが立つ要素がない場合、0～(M-1)のうち(1<<(d-1))のbitが立つ値の数だけ解に計上される
• Aの要素がすべて(1<<(d-1))のbitが立つ場合、0～(M-1)のうち(1<<(d-1))のbitが立たない値の数だけ解に計上される

これを踏まえ、dを大きい順に再帰的に処理していく。

int N;
ll M;


ll dfs(vector<int> A,int M,int d) {
	if(d==0||M==0) return 0;
	ll ret=0;
	vector<int> B[2];
	int m=(1<<(d-1));
	FORR(a,A) {
		if(a&m) {
			a-=m;
			B[1].push_back(a);
		}
		else B[0].push_back(a);
	}
	
	if(M==1<<d) {
		if(B[0].size()&&B[1].size()) {
			ret=dfs(B[0],m,d-1)+dfs(B[1],m,d-1);
		}
		else {
			ret=2*dfs(A,m,d-1)+1LL*m*m;
		}
		return ret;
	}
	if(B[0].size()) {
		ret=dfs(B[0],min(M,m),d-1);
	}
	else {
		ret=dfs(B[1],min(M,m),d-1)+(1LL*m)*min(M,m);
	}
	if(M>m) {
		if(B[1].size()) {
			ret+=dfs(B[1],M-m,d-1);
		}
		else {
			ret+=dfs(B[0],M-m,d-1)+(1LL*m)*(M-m);
		}
	}
	
	return ret;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	vector<int> A(N);
	FOR(i,N) cin>>A[i];
	
	cout<<dfs(A,M,30)<<endl;
}

まとめ

方針は合ってたはずなんだけど、なんか解が合わなかった。