mayoko’s diary

プロコンとかいろいろ。

東京工業大学プログラミングコンテスト2015 E - マス目色ぬり

想定解とは別の方法で解いてしまったっぽいです。

解法

K 個の塗り直されたパネルを特別パネルということにします。

この K 個の特別パネルのうち, いくつのパネルを使うかで 2^K 通りの場合分けをします...というのが大まかな方針です。もう少し細かいところを詰めていくために少し観察をします。

まず, 特別パネルが全く無い場合を考えます。この場合に R*C の長方形を考えると, 赤と青のパネルの差は以下のようになります。
・R*C が奇数の場合は, 左上のパネルの色のほうがもう一方の色のパネルより 1 多くなる
・R*C が偶数の場合は, どちらのパネルも同じ数になる

では次に, このパネルの中に特別パネルがある場合どうなるかを考えます。明らかなように, 赤が青に変化するなら赤の数が 1 個減って, 青の数が 1 個増えます。逆も同様です。

この観察からは, 次のこともわかります:「特別パネルがないところは, 特に考えなくても OK」
つまり, 「特別パネルのうち長方形の中に入れるものを選ぶ」というのを選び方によって全探索して, その長方形の赤, 青のパネルの差を求めていけば良いです。

ただ, これだけだとやや不完全です。例えば, 3*3 の正方形で, 真ん中の点(頂点(2, 2)) だけが特別パネルであるとしましょう。この場合, パネルの様子は以下のようになります。
RBR
BBB
RBR
よって, 答えは 3 個のはずです。ですが, 上で言ったような選び方しか考えないと, 探索では (2, 2) の頂点のみという長方形しか考えていません。じゃあどうするのかというと, 「上, 下, 右, 左に一ます分だけ余計に長方形の枠を広げることを許す」ということをやると解決します。

適当かよ, と思うかもしれないですがこれで良いです。なぜかというと, 枠を 2 つ以上広げることは意味がないからです。これは, 先ほど上で行った R*C の偶奇による場合分けと同じです。
枠を 2 つ広げると, 必ず R*C は偶数になるので, 赤と青の特別パネル以外での差は 0 になります。一方, 枠を 3 つ以上広げると, R*C は偶数か奇数かよくわかりませんが, どちらにしても枠を 1 つ広げたか, 1 つも広げてない場合と同じになります。

ということで, 結局, 「長方形内部に存在させる特別パネルの集合」および「上下右左に 1 マス拡張するか」という場合分けをして赤と青のパネルの差を全探索すれば良いです。

const int MAXK = 12;
int Y[MAXK], X[MAXK];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, K;
    cin >> N >> K;
    for (int i = 0; i < K; i++) {
        cin >> Y[i] >> X[i];
        Y[i]--; X[i]--;
    }
    int ans = 1;
    for (int s = 1; s < (1<<K); s++) {
        int lx = N, rx = 0, uy = N, dy = 0;
        for (int i = 0; i < K; i++) {
            if ((s>>i)&1) {
                lx = min(lx, X[i]);
                rx = max(rx, X[i]);
                uy = min(uy, Y[i]);
                dy = max(dy, Y[i]);
            }
        }
        for (int l = 0; l < 2; l++) for (int r = 0; r < 2; r++) {
            for (int u = 0; u < 2; u++) for (int d = 0; d < 2; d++) {
                int LX = lx, RX = rx, UY = uy, DY = dy;
                if (l == 1 && LX > 0) LX--;
                if (r == 1 && RX < N-1) RX++;
                if (u == 1 && UY > 0) UY--;
                if (d == 1 && DY < N-1) DY++;
                int ns = s;
                for (int i = 0; i < K; i++) {
                    if (LX <= X[i] && X[i] <= RX && UY <= Y[i] && Y[i] <= DY) ns |= 1<<i;
                }
                int blue = 0, red = 0;
                {
                    int mul = (RX-LX+1) * (DY-UY+1);
                    if (mul%2) {
                        if ((LX+UY)%2 == 0) red++;
                        else blue++;
                    }
                }
                for (int i = 0; i < K; i++) {
                    if ((ns>>i)&1) {
                        if ((Y[i]+X[i])%2 == 0) {
                            red--;
                            blue++;
                        } else {
                            red++;
                            blue--;
                        }
                    }
                }
                ans = max(ans, abs(blue-red));
            }
        }
    }
    cout << ans << endl;
    return 0;
}