はまやんはまやんはまやん

hamayanhamayan's blog

National Railway [AtCoder Beginner Contest 210 D]

競技プログラミング

https://atcoder.jp/contests/abc210/tasks/abc210_d

解説

https://atcoder.jp/contests/abc210/submissions/24331674

難しい問題。
なお、i,jをx,yと言い換えて説明している。

何から始めるか

問題の中で一番厄介な部分が絶対値であり、これをどうしようか考える。
2つのマスについて

2  
 1

みたいになっていれば1の方がxもyも大きいので、絶対値を外した計算ができる。
具体的には、

A[y1][x1] + A[y2][x2] + C×(y1 - y2 + x1 - x2)

となる。絶対値が外れるおかげで、以下のように変換できる。

A[y1][x1] + A[y2][x2] + C×(y1 - y2 + x1 - x2)
= { A[y1][x1] + C×(y1 + x1) } + { A[y2][x2] - C×(y2 + x2) }

前提として左上と右下の組になっていれば、このように2つの値を独立して考えることができるようになる。
こうすることで、1番目のマスを全探索し、1番目のマスを固定して、最適な2番目のマスを高速に求めることで解くことができる。
1番目のマスが固定されれば、2番目のマスを1番目のマスよりも左上にあるマスで{ A[y2][x2] - C×(y2 + x2) }が最大のものが最適解となる。
これは矩形区画の最大値を求める問題になるので高速に求められそうな感じがする（実際できる）

ここまでの理解がまずは重要。

位置の前提は適切か？

実は

 2  
1

というパターンもあり、その場合はこれに対応できない。
これを解決するために盤面を90度回転して同様の問題を解くというものがある。
盤面を90度回転させると、左下と右上の組について、左上と右下の組として考えることができるので、
回転させて同じ問題を解くと、考慮できなかったパターンも含めることができる。
なので、「そのまま解く」と「90度回転させて解く」の最適解が答えとなる。

2番目の最適なマスは？

1番目のマスを固定したときの最適な2番目のマスを求める方法について考えよう。
1番目のマスが(x1, y1)であるとき、最適な2番目のマス(x2, y2)が満たすべき条件は以下のようになる。

  • x2≦x1、かつ、y2≦y1、かつ、(x1,y1)!=(x2,y2)
  • A[y2][x2] - C×(y2 + x2)が条件を満たすものの中で最小

よくよく見るとほぼ矩形の領域に対して最小値を考えるというものであるが、矩形の領域に対して最小値を考える問題を少しもじればいいので、
矩形の領域に対する最小値を求めることを考える。
これには累積和というか、DPというかを前計算しておくことで対応する。

mi[y][x] := (1,1)～(x,y)の矩形領域のA[y2][x2] - C×(y2 + x2)の最小値

これの計算は

mi[y][x] = min(A[y][x] - C×(y + x), mi[y-1][x], mi[y][x-1])

という感じにすれば問題ない（領域外参照に注意すること）。
これで完全な矩形に対する最小値は求まった。
今回求めたいのは完全な矩形ではなく、(x1,y1)は使えないので、単にmin(mi[y1-1][x1], mi[y1][x1-1])を使えばいい。

これでACに必要な要素は整ったので、全部実装すれば解ける。

int H, W, C;
vector<vector<int>> A;
//---------------------------------------------------------------------------------------------------
ll mi[1010][1010];
ll solve() {
    rep(y, 0, H) rep(x, 0, W) mi[y][x] = A[y][x] - 1LL * C * (y + x);
    rep(y, 0, H) rep(x, 0, W) {
        if (0 < y) chmin(mi[y][x], mi[y - 1][x]);
        if (0 < x) chmin(mi[y][x], mi[y][x - 1]);
    }

    ll res = infl;
    rep(y, 0, H) rep(x, 0, W) {
        ll opt = infl;
        if (0 < y) chmin(opt, mi[y - 1][x]);
        if (0 < x) chmin(opt, mi[y][x - 1]);
        chmin(res, A[y][x] + 1LL * C * (y + x) + opt);
    }

    return res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W >> C;
    A.resize(H);
    rep(y, 0, H) rep(x, 0, W) {
        int a; cin >> a;
        A[y].push_back(a);
    }

    ll ans = infl;
    rep(_, 0, 2) {
        chmin(ans, solve());
        A = rotateClockwise(A);
        swap(H, W);
    }
    cout << ans << endl;
}