Codeforces Global Round 29 : E. Maximum OR Popcount

なんとか間に合った。
https://codeforces.com/contest/2147/problem/E

問題

整数列Aが与えられる。
以下のクエリに順次答えよ。

• 正整数Bが与えられる。Aの要素を合計B回までインクリメントできるとき、Aのbitwise-orのpopcountをいくつにできるか。

解法

元のAのbitwise-orに対し、まだ0のままのbitを1にする際、最小何回インクリメントが必要かを考えていこう。
i bit目を1にするために、i bit目未満が0になってしまうケースがあるので、そこもそれぞれ1に戻す最小インクリメント回数を求めておこう。

int T,N,Q;
ll A[202020];
ll ret[35];
int num[35];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>Q;
		ZERO(num);
		FOR(i,N) {
			cin>>A[i];
			FOR(j,35) if(A[i]&(1LL<<j)) num[j]++;
		}
		int sum=0;
		FOR(i,35) if(num[i]) sum++;
		FOR(i,35) {
			if(i<=sum) ret[i]=0;
			else ret[i]=1LL<<30;
		}
		ll tot=0;
		FOR(i,35) if(num[i]==0) {
			sum++;
			for(j=i;j>=0;j--) if(num[j]==0) {
				x=0;
				ll dif=1LL<<35;
				FOR(k,N) {
					ll d=(1LL<<j)-(A[k]&((1LL<<j)-1));
					if(d<dif) {
						dif=d;
						x=k;
					}
				}
				tot+=dif;
				num[j]++;
				A[x]|=1LL<<j;
				FOR(k,j) if(A[x]&(1LL<<k)) {
					A[x]^=1LL<<k;
					num[k]--;
				}
			}
			ret[sum]=tot;
		}
		
		while(Q--) {
			cin>>x;
			int ma=0;
			FOR(i,35) if(ret[i]<=x) ma=i;
			cout<<ma<<endl;
		}
		
		
		
	}
}

まとめ

これはありそうな問題に見えたけど、意外に珍しいのか。