第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 で教えてもらいました。
@mayoko_ 累積和をとります。右端rを決めます。sum[r]-min(sum[l] : 0<=l<r )が右端がrである区間の和の最大になります。rを増やしながらやれば最小がいい感じにとれて線形って感じです
— (nは自然数) (@n_vip) 2016, 1月 23
典型らしいのですぐ思いつかないとマズかったですね…
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; }