yukicoder : No.3293 Golden Cross

方針立ったと思ったけど、細かいところが足りてなかった。
https://yukicoder.me/problems/no/3293

問題

行列Aが与えられる。
交差値CはAと同じサイズで、C(r,c) := (Aのr行目の総和)*(Aのc行目の総和) で適宜される。
また、SはCの要素の最大値とする。

Aと同じサイズの行列Bが与えられる。コストを2^(B(r,c))かけると、A(r,c)をインクリメントできるとする。
コストK以下で、Sをどこまで大きくできるか。

解法

C(r,c)を総当たりし、どこまで大きくできるかを考える。
インクリメントする対象は、以下の3つの候補がある。

• A(r,c)
• A(r,c)以外で、r行目のうちコストが最小の要素
• A(r,c)以外で、c列目のうちコストが最小の要素

なお、3つのコストの大小関係によって、実際に3つ全部をインクリメントして得することはなく、2つだけで良い。
また、その場合2つの要素のうち片方のインクリメント回数に対し、C(r,c)の値が二次関数を成す。
よって、その極大値を解の候補をすればよい。

int H,W;
ll K;
ll A[1010][1010],B[1010][1010];
ll R[1010],C[1010];
vector<int> RC[1010];
vector<int> CC[1010];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>K;
	FOR(y,H) FOR(x,W) {
		cin>>A[y][x];
		R[y]+=A[y][x];
		C[x]+=A[y][x];
	}
	FOR(y,H) FOR(x,W) {
		cin>>B[y][x];
		RC[y].push_back(B[y][x]);
		CC[x].push_back(B[y][x]);
	}
	FOR(y,H) sort(ALL(RC[y]));
	FOR(x,W) sort(ALL(CC[x]));
	ll ret=0;
	FOR(y,H) FOR(x,W) {
		ll X=A[y][x];
		ll Y=R[y]-X;
		ll Z=C[x]-X;
		int YC=RC[y][0];
		int ZC=CC[x][0];
		int XC=B[y][x];
		if(YC==XC) YC=RC[y][1];
		if(ZC==XC) ZC=CC[x][1];
		
		FOR(i,2) {
		
			if(XC<=YC&&XC<=ZC) {
				ll add=K>>XC;
				ret=max(ret,(X+add+Y)*(X+add+Z));
			}
			else if(XC>=YC+ZC) {
				// YとZ
				vector<ll> cand={0,K>>YC};
				ll TY=(((X+Z)<<ZC)+K-((X+Y)<<YC))>>(1+YC);
				cand.push_back(TY-1);
				cand.push_back(TY);
				cand.push_back(TY+1);
				FORR(ty,cand) if(ty>=0&&((ty<<YC)<=K)) {
					ll tz=(K-(ty<<YC))>>ZC;
					ret=max(ret,(X+ty+Y)*(X+tz+Z));
				}
				
			}
			else if(XC>YC) {
				// XとY
				vector<ll> cand={0,K>>XC};
				ll TX=(((X+Z)<<YC)+K-((X+Y)*((1LL<<XC)-(1LL<<YC))))/(2*((1LL<<XC)-(1LL<<YC)));
				cand.push_back(TX-1);
				cand.push_back(TX);
				cand.push_back(TX+1);
				FORR(tx,cand) if(tx>=0&&((tx<<XC)<=K)) {
					ll ty=(K-(tx<<XC))>>YC;
					ret=max(ret,(X+tx+Y+ty)*(X+tx+Z));
				}
				
			}
			swap(Y,Z);
			swap(YC,ZC);
		}
		
	}
	cout<<ret<<endl;
	
	
}

まとめ

なるほど…。