AtCoder ABC #147 : E - Balanced Path

今回難易度上がってたみたいね。
https://atcoder.jp/contests/abc147/tasks/abc147_e

問題

H*Wのグリッドがあり、各セルに2つずつ値が設定されている。
まず、各セルの2値をどちらか青、どちらか赤に任意に設定する。
その後、左上から右または下の隣接マスを辿り右下のマスに移動することを考える。

移動経路における青の値から赤の値を引いたものの総和を考えたとき、その絶対値の最小値を求めよ。

解法

2値あるのは面倒なので、差を足すか引くかの2通りと考えると値は1通りで符号だけの違いとなる。
幸いこの問題はグリッドのサイズも小さく、値の範囲も小さいので、愚直に全セルにおいてそこまでの差の総和がある値になるかどうかのbool値を全通り保持しても間に合う。
以下のコードはbitsetで多少高速化した。

int H,W;
int A[80][80];

bitset<160*176> B[80][80];

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) FOR(x,W) {
		cin>>r;
		A[y][x]=abs(A[y][x]-r);
	}
	B[0][0][80*165+A[0][0]]=1;
	FOR(y,H) FOR(x,W) {
		if(y+1<H) {
			B[y+1][x] |= B[y][x]<<A[y+1][x];
			B[y+1][x] |= B[y][x]>>A[y+1][x];
		}
		if(x+1<W) {
			B[y][x+1] |= B[y][x]<<A[y][x+1];
			B[y][x+1] |= B[y][x]>>A[y][x+1];
		}
	}
	
	int mi=101010;
	FOR(i,160*176) if(B[H-1][W-1][i]) mi=min(mi,abs(i-80*165));
	cout<<mi<<endl;
	
}

まとめ

bitset要らなさそう。