Codeforces #948 : Div2 D. XORificator

全完できず…。
https://codeforces.com/contest/1977/problem/D

問題

0/1で構成される行列が与えられる。
行を選択し、0/1反転させることができるとき、1が1個だけある列は最大何個作れるか。

解法

各列、どの行に1を残すかを定めると行の反転のバリエーションが定まる。
逆に、行の反転のバリエーションが一致する列数の最大値を求めればよい。
反転する行のリストを、ハッシュ値の和で取れば反転する列の一致を高速に反転できる。

int T,H,W;
string S[303030];

map<pair<ll,ll>,vector<pair<int,int>>> M;
const ll mo=1000000007;
ll p2[303030];
ll p3[303030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	p2[0]=p3[0]=1;
	FOR(i,301010) p2[i+1]=p2[i]*2%mo,p3[i+1]=p3[i]*3%mo;
	
	
	
	cin>>T;
	while(T--) {
		cin>>H>>W;
		FOR(y,H) cin>>S[y];
		M.clear();
		pair<ll,ll> v;
		FOR(x,W) {
			ll cur1=0,cur2=0;
			FOR(y,H) if(S[y][x]=='1') cur1+=p2[y],cur2+=p3[y];
			FOR(y,H) {
				ll a=cur1,b=cur2;
				if(S[y][x]=='1') {
					a-=p2[y],b-=p3[y];
				}
				else {
					a+=p2[y],b+=p3[y];
				}
				M[{a,b}].push_back({x,y});
				if(M[{a,b}].size()>M[v].size()) v={a,b};
			}
		}
		int ret=M[v].size();
		int x1=M[v][0].first;
		int y1=M[v][0].second;
		string V;
		FOR(y,H) {
			if(y==y1) V+=S[y][x1]^1;
			else V+=S[y][x1];
		}
		cout<<ret<<endl;
		cout<<V<<endl;
		
	}
}

まとめ

ハッシュが思いついてよかったね。