Codeforces #584 E2. Rotate Columns (hard version)

まぁまぁの出来だった回。
https://codeforces.com/contest/1209/problem/E2

問題

N*Mの行列が与えられる。
各列において、その要素を任意回数rotateできるものとする。
各行の最大値の総和の最大値はいくつか。

解法

最終的にM列分しか答えに反映されない。
そこで、各列最大値が上位M位に入るものを残そう。

あとはBitDPで、最大値未確定の行にうまくrotateで各列の最大値を当てはめていくよう総当たりしよう。
1つの列が複数行カバーするケースもあるので注意。

int T;
int A[2020][2020];
int H,W;
int from[1<<12],to[1<<12],sum[1<<12];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>W>>H;
		FOR(y,W) FOR(x,H) cin>>A[x][y];
		vector<pair<int,int>> V;
		FOR(y,H) {
			i=*max_element(A[y],A[y]+W);
			V.push_back({i,y});
		}
		sort(ALL(V));
		reverse(ALL(V));
		if(V.size()>W) V.resize(W);
		
		ZERO(from);
		FORR(v,V) {
			ZERO(sum);
			int mask=0;
			FOR(mask,1<<W) {
				int s=0;
				FOR(i,W) if(mask&(1<<i)) s+=A[v.second][i];
				int cmask=mask;
				FOR(i,W) {
					sum[cmask]=max(sum[cmask],s);
					cmask=((cmask<<1) | (cmask>>(W-1))) & ((1<<W)-1);
				}
			}
			
			ZERO(to);
			FOR(mask,1<<W) {
				int cand=((1<<W)-1)^mask;
				for(int cm=cand; cm>=0; cm--) {
					cm&=cand;
					to[mask|cm]=max(to[mask|cm],from[mask]+sum[cm]);
				}
			}
			
			swap(from,to);
		}
		
		cout<<from[(1<<W)-1]<<endl;
		
		
	}
}

まとめ

本番これはそんなに苦労してないな。