問題はこちら
マス に二つの数 が書かれている.一回の移動で または に移動する.マス から に移動しながら,数の片方を選び に.もう片方を に追加する.移動する経路を とする時,以下の値を偏りと呼ぶ.
数を自由に選びながら移動した時の,偏りの最小値を求めよ.
制約は以下の通り.
考え方
まずは式変形から.
つまり,経路を辿りながら値の差を足し合わせ,最後に絶対値をとる事と等しい.全ての経路を全列挙するのは 程度かかるので間に合わない.今回の場合は,制約が非常に小さいことに注意する.具体的には,答えとなりうる偏りは最大でも .
そこで,今のマス目でありうる符号付偏りの値を,毎回更新することを考え,最後に絶対値をとることにする.具体的には,以下のようなbool配列でdpをする.
dp[i][j][l]
:= マス目 で符号付偏り となるかどうか
( が負の時はどうするのか?という話があるが,それは解答のところで説明することにする.一旦無視する.)
マス目 での符号付偏りが とする .マス目 から に移動した時,そのマス目までで取りうる値は次のようになる.
よって,更新式は次の通り. を取りうる場合は,新しい値も更新するようにする.
if dp[i][j][l] == true then dp[i+1][j][l + B[i+1][j] - A[i+1][j]] = true; dp[i+1][j][l - B[i+1][j] + A[i+1][j]] = true;
マス目 に移動するときも同様に考えれば良い.
解答
実装上の注意として,経路の途中で負となりうる場合はどうするかというのがある.editorialだと毎回絶対値をとっていたが,自分の実装では配列を「最大の偏り * 2」だけのサイズを取り,全ての値に「最大の偏り」分を足すことで負のindexにアクセスしないようにした.
#include <bits/stdc++.h> using namespace std; using ll = long long; #define rep(i, n) for(ll i = 0; i < (ll)(n); i++) int main() { ll h, w; cin >> h >> w; int a[h][w], b[h][w]; rep(i, h) rep(j, w) cin >> a[i][j]; rep(i, h) rep(j, w) cin >> b[i][j]; ll max_diff = 2 * 80 * 160; bool dp[h][w][max_diff]; rep(i, h) rep(j, w) rep(l, max_diff) dp[i][j][l] = false; ll mid = max_diff / 2; dp[0][0][b[0][0] - a[0][0] + mid] = true; dp[0][0][-b[0][0] + a[0][0] + mid] = true; rep(i, h) { rep(j, w) { rep(l, max_diff) { if (!dp[i][j][l]) continue; if (i + 1 <= h - 1) { dp[i + 1][j][l + b[i + 1][j] - a[i + 1][j]] = true; dp[i + 1][j][l - b[i + 1][j] + a[i + 1][j]] = true; } if (j + 1 <= w - 1) { dp[i][j + 1][l + b[i][j + 1] - a[i][j + 1]] = true; dp[i][j + 1][l - b[i][j + 1] + a[i][j + 1]] = true; } } } } ll ans = 1e18; rep(i, max_diff) { if (dp[h - 1][w - 1][i]) ans = min(ans, abs(i - mid)); } cout << ans << '\n'; }
Submission #8980170 - AtCoder Beginner Contest 147
参考
とてもわかりやすかった.