ABC147 E - Balanced Path (500)

E - Balanced Path

概要

H × WのグリッドとH × Wの整数の配列A, Bが与えられる。
グリッドを右もしくは下に移動して(0,0)から(H-1,W-1)に移動する経路を考える。同時に経路に対応するA, Bの数値のいずれかを赤、もう片方を青色に塗り分ける。
各経路について、「(赤く塗った数字の和-青く塗った数字の和)の絶対値」を偏りと呼ぶ。偏りの最小値を求めよ。

制約

2 ≦ H, W ≦ 80
0 ≦ A[i][j], B[i][j] ≦ 80

方針

数字の塗り分けを考えることは、「移動直前の偏りをkとし、移動先のマス(i, j)についてd=abs(A[i][j] - B[i][j])とした際に、移動後の偏りをabs(k-d)とするかabs(k+d)とするか」を考えることと同値である。

偏りの最大値は緩く見積もっても移動経路長*max(A[i][j], B[i][j]) ≦ 160 * 80である。
ここでdp[i][j][k] := 現在(i-1, j-1)マスにいるとき、偏りがkになることがあるか　というDP配列を考えると、配列サイズは2 * 80 * 80 * 160 * 80 = 163MB程度であり、空間計算量の制約を満たす。よって、上記のdpを行う。

感想

bitset高速化を用いなくても通るようでした。

解答

Submission #9022147 - AtCoder Beginner Contest 147

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
const int max_k = 160 * 80;
bool dp[81][81][max_k+1];
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int h, w;
	cin >> h >> w;
 
	int a[h][w];
	rep(i, h) rep(j, w) cin >> a[i][j];
 
	int b[h][w];
	rep(i, h) rep(j, w) cin >> b[i][j];
 
	rep(i, 81) rep(j, 81) rep(k, max_k+1) dp[i][j][k] = false;
	dp[0][1][0] = true;
	dp[1][0][0] = true;
 
	rep(i, h) rep(j, w) rep(k, max_k+1){
		int d = abs(a[i][j] - b[i][j]);
 
		if(k + d <= max_k) dp[i+1][j+1][k + d] |= dp[i+1][j][k];
		if(abs(k - d) <= max_k) dp[i+1][j+1][abs(k - d)] |= dp[i+1][j][k];
		if(k + d <= max_k) dp[i+1][j+1][k + d] |= dp[i][j+1][k];
		if(abs(k - d) <= max_k) dp[i+1][j+1][abs(k - d)] |= dp[i][j+1][k];
 
	}
 
	rep(k, max_k + 1) {
		if(dp[h][w][k]) {
			cout << k << endl;
			return 0;
		}
	}
}