ひらめの日常

日常のメモをつらつらと

AtCoder: ABC147-E Balanced Path (500)

問題はこちら

atcoder.jp

マス  (i,j) に二つの数  A _ {ij}, B_ {ij} が書かれている.一回の移動で  (i+1, j) または  (i, j +1) に移動する.マス  (0, 0) から  (H, W) に移動しながら,数の片方を選び  X に.もう片方を  Y に追加する.移動する経路を  p とする時,以下の値を偏りと呼ぶ.

  •  |\sum{X_p} - \sum{Y_p}|

数を自由に選びながら移動した時の,偏りの最小値を求めよ.

制約は以下の通り.

  •  2\leq H\leq 80, 2\leq W\leq 80
  •  0\leq A _ {ij}\leq 80, 0\leq B _ {ij} \leq 80

考え方

まずは式変形から.

 |\sum{X_p} - \sum{Y_p}| = |\sum{(X_p - Y_p)}|

つまり,経路を辿りながら値の差を足し合わせ,最後に絶対値をとる事と等しい.全ての経路を全列挙するのは   _ {H+W}C _ {H} 程度かかるので間に合わない.今回の場合は,制約が非常に小さいことに注意する.具体的には,答えとなりうる偏りは最大でも  80 * (80+80).

そこで,今のマス目でありうる符号付偏りの値を,毎回更新することを考え,最後に絶対値をとることにする.具体的には,以下のようなbool配列でdpをする.

  • dp[i][j][l] := マス目  (i, j) で符号付偏り  l となるかどうか

 l が負の時はどうするのか?という話があるが,それは解答のところで説明することにする.一旦無視する.)

マス目  (i, j) での符号付偏りが  lとする .マス目  (i, j) から  (i+1, j) に移動した時,そのマス目までで取りうる値は次のようになる.

  •  l + (B _ {i+1\ j} - A _ {i+1\ j})
  •  l + (A _ {i+1\ j} - B _ {i+1\ 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;

マス目  (i, j+1) に移動するときも同様に考えれば良い.

解答

実装上の注意として,経路の途中で負となりうる場合はどうするかというのがある.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

参考

とてもわかりやすかった.

[AtCoder 参加感想] 2019/12/08:ABC 147 | maspyのHP