AtCoder ARC #135 : D - Add to Square

Dは何とか解けた。
https://atcoder.jp/contests/arc135/tasks/arc135_d

問題

H*Wの行列が与えられる。
2*2の領域を指定し、同じ数を加算する、という処理を任意回数行えるとする。
最終的に各要素の絶対値の総和の最小値を求めよ。

解法

2*2の領域を1つずつずらしながら、±逆にして交互に同じ数を加算していくことで、あるR*Cの矩形領域に対し角の4要素のみ絶対値が同じ値を加算した状態を作ることができる。
その際の符号は、R,Cの偶奇による。

まず、右下から順に、極力0を作っていく。
そうすると、1行目と1列目以外は0ができる。
あとは1行目のどこかの列と、1列目のどこかの行を総当たりし、その2要素を角とするような矩形を選択しよう。
四つ角に±aだけ加算すると、最大3*|a|だけ絶対値の総和を減らすことができるaが取れる場合がある。

int H,W;
ll A[505][505];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	FOR(y,H) FOR(x,W) cin>>A[y][x];
	for(y=H-2;y>=0;y--) {
		for(x=W-2;x>=0;x--) {
			ll v=A[y+1][x+1];
			A[y][x]-=v;
			A[y][x+1]-=v;
			A[y+1][x]-=v;
			A[y+1][x+1]-=v;
		}
	}
	/*
	FOR(y,H) {
		FOR(x,W) cout<<A[y][x]<<" ";
		cout<<endl;
	}
	*/
	for(y=1;y<H;y++) for(x=1;x<W;x++) {
		
		ll mi=0;
		if(x%2==y%2) {
			if(A[y][0]>0&&A[0][x]>0) mi=min(A[y][0],A[0][x]);
			if(A[y][0]<0&&A[0][x]<0) mi=max(A[y][0],A[0][x]);
			A[y][0]-=mi;
			A[0][x]-=mi;
			if(x%2==0) {
				A[y][x]+=mi;
				A[0][0]+=mi;
			}
			else {
				A[y][x]-=mi;
				A[0][0]-=mi;
			}
		}
		else if(x%2==1) {
			if(A[y][0]<0&&A[0][x]>0) mi=min(-A[y][0],A[0][x]);
			if(A[y][0]>0&&A[0][x]<0) mi=max(-A[y][0],A[0][x]);
			A[0][0]-=mi;
			A[y][0]+=mi;
			A[0][x]-=mi;
			A[y][x]+=mi;
		}
		else {
			if(A[y][0]>0&&A[0][x]<0) mi=min(A[y][0],-A[0][x]);
			if(A[y][0]<0&&A[0][x]>0) mi=max(A[y][0],-A[0][x]);
			A[0][0]-=mi;
			A[y][0]-=mi;
			A[0][x]+=mi;
			A[y][x]+=mi;
		}
		
		
	}
	
	ll sum=0;
	FOR(y,H) FOR(x,W) sum+=abs(A[y][x]);
	cout<<sum<<endl;
	FOR(y,H) {
		FOR(x,W) cout<<A[y][x]<<" ";
		cout<<endl;
	}
}

まとめ

符号の反転でだいぶ混乱した。