Deltix Round Spring 2021 : D. Love-Hate

なんか妙に出来が良かった回。
https://codeforces.com/contest/1523/problem/D

問題

N個のM bit値が与えられる。各値は、高々P bitしか立っていない。

M bit中いくつかの桁を選び、N個のうち過半数でそのbitが立っているようにしたい。
選べる桁の最大値を求めよ。

解法

N個のうち過半数でそのbitが立つということは、もしその過半数に入る1個の値を特定できれば、解はそのM bit値のsubmaskである。
そこで、乱択を20回程度繰り返し、過半数がわに入れるべき1個の値を選ぼう。
あとは高速ゼータ変換の要領で、M bit値のsubmaskごとに同じmaskを持つ値の数を数え上げ、N個の過半数を占めるmaskを総当たりしよう。

int N,M,P;
string S[202020];

int sum[1<<15];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>P;
	FOR(y,N) cin>>S[y];
	vector<int> ret;
	srand(time(NULL)+i);
	FOR(i,20) {
		x=(rand()+1LL*rand()*rand()+i)%N;
		vector<int> cand;
		ZERO(sum);
		FOR(j,M) if(S[x][j]=='1') cand.push_back(j);
		P=cand.size();
		FOR(j,N) {
			int mask=0;
			FOR(k,cand.size()) if(S[j][cand[k]]=='1') mask|=1<<k;
			sum[mask]++;
		}
		
		FOR(j,P) {
			FOR(y,1<<P) if((y&(1<<j))==0) sum[y]+=sum[y|(1<<j)];
		}
		FOR(y,1<<P) if(sum[y]>=(N+1)/2) {
			if(__builtin_popcount(y)>ret.size()) {
				ret.clear();
				FOR(j,P) if(y&(1<<j)) ret.push_back(cand[j]);
			}
		}
		
	}
	
	string R(M,'0');
	FORR(v,ret) R[v]='1';
	cout<<R<<endl;
	
}

まとめ

今日のABCもそうだけど、過半数ときたら乱択を思い浮かべないとな。