mayoko’s diary

プロコンとかいろいろ。

第2回 ドワンゴからの挑戦状 予選 D - 庭園

第2回 ドワンゴからの挑戦状 予選 に参加しました。結果はあんまり良くなかったですが 17 卒パワーで予選通過したと思います。

解法

まず考察です。

memox[x1][x2] = (長方形の x1 〜 x2 を使うと決めた時, y1, y2 を最適に選んで (y1, x1) 〜 (y2, x2) の範囲のきれいさを最大化したときのきれいさの値) とすると, memox[x1][x2] + memox[x3][x4] を最大化する, という方針が考えられます。しかし, この方針では, 2 つの長方形が重なってしまう恐れがあります。例えば, x1 = 2, x2 = 5 の時の最適な y1, y2 の範囲が y1 = 4, y2 = 8 で, x3 = 3, x4 = 8 の時の最適な y3, y4 の範囲が y3 = 6, y4 = 9 だったりすると, 2つの長方形は重なってしまい, 問題の条件に合いません(図を書いて確かめてみて下さい)。
これに対策するために, x1, x2 と x3, x4 の区間が重ならないようにすると, x1, x2 と x3, x4 の区間が重なる場合を考えないことになるので, やっぱりダメです。
しかし, よく考えると, x1, x2 と x3, x4 の区間が重なるような場合は, y1, y2 と y3, y4 の区間は重なりません。よって, 「x1, x2 と x3, x4 が重ならない場合」と「y1, y2 と y3, y4 が重ならない場合」を考えれば, すべての場合を出し尽くしたことになります。

よって, memox, memoy を作れば, とりあえず O(n^4) みたいな解は作れます。これで部分点です。

memox を使うと, dpx[x1][x3] = (x1 <= x2 < x3 を満たす x2 について, memox[x1][x2] が最大になる時の値) というのが各 dpx[x1][x3] について O(n) で求められ, これを使うと「x1, x2 と x3, x4 が重ならない場合」のきれいさの最大値は, x1 と x3 を決めて, dpx[x1][x3] + dpx[x3][W+1] を求めれば良いので O(n^2) で出来ます。

よって, あと問題なのは memox[x1][x3] を O(n^3) で求めることです。
これは 1 次元の区間の最大を求める問題に帰着しますが, Twitter で教えてもらいました。

典型らしいのですぐ思いつかないとマズかったですね…

const int MAX = 333;
const ll INF = 1ll<<55;
ll B[MAX][MAX];
ll total[MAX][MAX];
ll memoy[MAX][MAX];
ll memox[MAX][MAX];
ll dpy[MAX][MAX];
ll dpx[MAX][MAX];

ll getSum(int y1, int x1, int y2, int x2) {
    return total[y2][x2] - total[y2][x1-1] - total[y1-1][x2] + total[y1-1][x1-1];
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int H, W;
    cin >> H >> W;
    for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) {
        cin >> B[i][j];
    }
    for (int i = 1; i <= H; i++) for (int j = 1; j <= W; j++) {
        total[i][j] = total[i-1][j] + total[i][j-1] - total[i-1][j-1] + B[i-1][j-1];
    }
    // memo
    for (int y1 = 1; y1 <= H; y1++) for (int y2 = y1; y2 <= H; y2++) {
        memoy[y1][y2] = -INF;
        vector<ll> memo(W+1);
        for (int i = 1; i <= W; i++) memo[i] = min(memo[i-1], getSum(y1, 1, y2, i));
        for (int r = 1; r <= W; r++) memoy[y1][y2] = max(memoy[y1][y2], getSum(y1, 1, y2, r) - memo[r-1]);
    }
    for (int x1 = 1; x1 <= W; x1++) for (int x2 = x1; x2 <= W; x2++) {
        memox[x1][x2] = -INF;
        vector<ll> memo(H+1);
        for (int i = 1; i <= H; i++) memo[i] = min(memo[i-1], getSum(1, x1, i, x2));
        for (int r = 1; r <= H; r++) memox[x1][x2] = max(memox[x1][x2], getSum(1, x1, r, x2) - memo[r-1]);
    }
    // dp
    for (int x1 = 1; x1 <= W; x1++) for (int x3 = x1+1; x3 <= W+1; x3++) {
        dpx[x1][x3] = -INF;
        for (int x2 = x1; x2 < x3; x2++) dpx[x1][x3] = max(dpx[x1][x3], memox[x1][x2]);
    }
    for (int y1 = 1; y1 <= H; y1++) for (int y3 = y1+1; y3 <= H+1; y3++) {
        dpy[y1][y3] = -INF;
        for (int y2 = y1; y2 < y3; y2++) dpy[y1][y3] = max(dpy[y1][y3], memoy[y1][y2]);
    }
    // solve
    ll ans = -INF;
    for (int x1 = 1; x1 <= W; x1++) for (int x3 = x1+1; x3 <= W; x3++) {
        ans = max(ans, dpx[x1][x3] + dpx[x3][W+1]);
    }
    for (int y1 = 1; y1 <= H; y1++) for (int y3 = y1+1; y3 <= H; y3++) {
        ans = max(ans, dpy[y1][y3] + dpy[y3][H+1]);
    }
    cout << ans << endl;
    return 0;
}