SRM 552 div1 med FoxAndFlowerShopDivOne

問題

H*W のグリッドが与えられる。各セルには 'P' か 'L' か '.' と書かれている。このグリッドから, 2 つの長方形を交差しないように選び, 以下の条件を満たすもとで 2 つの長方形内の 'L' の数 + 'P' の数を最大化したい。最大値を求めよ。

条件: 2 つの長方形内の 'L' の数と 'P' の数の差の絶対値は maxDiff 以下である。

解法

O(n^6) で無理やり通したんですが, O(n^5) がありました。

下の問題と設定が酷似しています。
mayokoex.hatenablog.com

今回もこのアイデアと同様, 「交差してない -> x 方向か y 方向で交差していない」ということを利用します。ということで, 方針としては,

左側の長方形の x0, x1 を決める
右側の長方形の x2, x3, y0, y1 を決めて, 各長方形について l-p の値ごとに l+p の値を最大化する(mp[l-p] = max(l+p) とメモしておく)
左側の長方形の y0, y1 を決めて, 各長方形について mp の情報を使って l+p を最大化する(mp をなめるのに O(n^2) かかる)

となります。これだと O(n^6) になりますが,

左側と右側を分ける x 座標 vx を決める
左側, 右側について長方形を O(n^4) で調べ, l-p の値ごとに l+p を最大化する(left, right という配列にメモ)
left, right を使って条件を満たす範囲で l+p を最大化する

とやれば O(n^5) になります。なるべく対称性を保つようにやると計算量削減しやすそうですね。

今のだと x 方向に交差しない場合しか考えてませんが長方形を 90 度回転させて同じことをやれば y 方向に交差しない場合も同じように求められます。

const int MAXN = 33;
const int B = MAXN*MAXN;
int sum[2][MAXN][MAXN];
int mp[2*B];

int getSum(int type, int y0, int x0, int y1, int x1) {
    return sum[type][y1][x1] - sum[type][y1][x0] - sum[type][y0][x1] + sum[type][y0][x0];
}
int calc(vector<string> flowers, int maxDiff) {
    memset(sum, 0, sizeof(sum));
    int H = flowers.size(), W = flowers[0].size();
    for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) {
        for (int k = 0; k < 2; k++)
            sum[k][i+1][j+1] = sum[k][i+1][j] + sum[k][i][j+1] - sum[k][i][j];
        if (flowers[i][j] == 'L') sum[0][i+1][j+1]++;
        if (flowers[i][j] == 'P') sum[1][i+1][j+1]++;
    }
    int ret = -1;
    for (int x0 = 0; x0 < W; x0++) for (int x1 = x0+1; x1 <= W; x1++) {
        memset(mp, -1, sizeof(mp));
        for (int y0 = 0; y0 < H; y0++) for (int y1 = y0+1; y1 <= H; y1++) {
            for (int x2 = x1; x2 < W; x2++) for (int x3 = x2+1; x3 <= W; x3++) {
                int l = getSum(0, y0, x2, y1, x3);
                int p = getSum(1, y0, x2, y1, x3);
                mp[l-p+B] = max(l+p, mp[l-p+B]);
            }
        }
        for (int y0 = 0; y0 < H; y0++) for (int y1 = y0+1; y1 <= H; y1++) {
            int l = getSum(0, y0, x0, y1, x1);
            int p = getSum(1, y0, x0, y1, x1);
            for (int i = max(0, -maxDiff+p-l+B); i <= min(2*B-1, maxDiff+p-l+B); i++) {
                if (mp[i] != -1) ret = max(ret, mp[i]+l+p);
            }
        }
    }
    return ret;
}

class FoxAndFlowerShopDivOne {
public:
    int theMaxFlowers(vector <string> flowers, int maxDiff) {
        int ret = -1;
        ret = max(ret, calc(flowers, maxDiff));
        int H = flowers.size(), W = flowers[0].size();
        vector<string> tmp(W);
        for (int i = 0; i < W; i++) {
            tmp[i].resize(H);
            for (int j = 0; j < H; j++) {
                tmp[i][j] = flowers[j][i];
            }
        }
        ret = max(ret, calc(tmp, maxDiff));
        return ret;
    }
};

mayoko’s diary

プロコンとかいろいろ。

SRM 552 div1 med FoxAndFlowerShopDivOne

問題

解法