http://arc081.contest.atcoder.jp/tasks/arc081_d

問題概要

H×Wの2次元のマス目が与えられる。各マスは白か黒のどちらかで塗られている。任意の行または列を選びその行または列に含まれるすべてのマスの色を反転させる、という操作を好きなだけ行えるとき、黒のマスだけで構成できる長方形の最大面積を求めよ。

H, W <= 2000

解法

なぜそうなるかは一旦置いて、解法のみ先に述べる。まず各行独立にxorで階差数列をとり、H×(W-1)の行列をつくる。この行列のj列目を見たときi行目～(i+x)行目の要素が全部同じであれば、元の行列のi行目～(i+x)行目, j列目～(j+1)列目を全部黒で塗りつぶして(x+1)×2の長方形を作ることができる。逆に異なる要素が出てきた場合、それ以上長方形を伸ばすことはできない。これは各列で独立に成り立つ。以上より解の構成は以下の手順で行うことができる。

各行独立にxorで階差数列をとってH×(W-1)の行列を作る
作った行列の各要素ごとに、「下方向にどれだけ同じ要素が続くか」を計算する
各行ごとに2で計算した値をヒストグラムのように見て「ヒストグラム中の長方形の最大面積」を計算する

2はO(HW)でできる。3も各行の面積最大化をO(W)で行えるのでO(HW)。あわせてO(HW)で答えが出る。コーナーケースとして、一行・一列だけで作れる最大の長方形を考慮に入れる必要がある（必ずH, Wになる）。以上で答えが求まった。

で、なぜそうなるのか？まず差分が同一なら長方形を縦に伸ばしていけることについて。差分が0であるのは横並びが白白または黒黒というパターンである。これが縦に並んでいるなら全部黒にできるのは自明である。逆に差分が1のとき、つまり横並びが白黒または黒白というパターンでは、一度どちらかの列に反転を入れればすべて白白または黒黒になる。あとは白白の行にだけ反転を入れていけば全部黒にできる。例↓

f:id:fluffyowl:20170822182857p:plain

逆に差分が異なる場合は長方形を伸ばすことが不可能である（公式解説でいう「悪い部分」）。まず横に反転操作を入れても階差行列の値に変化は起こらない。また縦に反転を入れると階差行列は列方向に全部同時に反転が起こる。ゆえにどうやっても上下の片方だけ差分を変える、ということができず、両方を差分0で揃えることができない＝黒黒にできない、ということになる。以上が差分が同じである限り縦に長方形を伸ばしていける理由である。

もう一点、以上の議論が列ごとに独立であることについて。先ほども述べた通り横方向に反転操作を行っても階差行列の方には一切の変化が生じない。また縦に入れても1列すべてが同時に反転するので「縦に見て同じかどうか」という関係には変化が生じない。以上より長方形を作るための反転操作をどのように行っても長方形作成にかかわる条件には影響がない。よって列ごとに独立に見ることができる。

感想

前回のARC-Fで「0/1数列の区間flipを考えるときは階差をみてみる」という考え方を知ったばかりなのに解けなかった。本番中は2次元で階差ってどうやるの？？？ふえ〜～んで終了。それがわかったところで長方形の面積最大化を知らないし思いつけない。ムズい。とりあえず、ヒストグラムの長方形面積最大化を知れたのと、階差をとるとはつまり変化を考えてそれを形式的に表すことである、という認識は得た。今後に期待

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;

void main() {
    auto s = readln.split.map!(to!int);
    auto H = s[0];
    auto W = s[1];
    auto A = H.iota.map!(_ => readln.chomp).array;
    auto B = new int[][](H, W);
    auto C = new int[][](H, W-1);
    foreach (i; 0..H) foreach (j; 0..W-1) C[i][j] = A[i][j] == A[i][j+1];

    fill(B[H-1], 1); B[H-1][W-1] = 0;
    for (int j = 0; j < W - 1; j++) {
        for (int i = H - 2; i >= 0; i--) {
            if (C[i+1][j] == C[i][j]) B[i][j] = B[i+1][j] + 1;
            else B[i][j] = 1;
        }
    }

    
    int ans = max(H, W);
    
    foreach (i; 0..H) {
        DList!(Tuple!(int, int)) stack;
        foreach (j; 0..W) {
            if (stack.empty || stack.back[1] < B[i][j]) {
                stack.insertBack(tuple(j, B[i][j]));
            } else {
                int pos = j;
                while (!stack.empty && stack.back[1] > B[i][j]) {
                    int area = (j - stack.back[0] + 1) * stack.back[1];
                    ans = max(ans, area);
                    pos = stack.back[0];
                    stack.removeBack;
                }
                stack.insertBack(tuple(pos, B[i][j]));
            }
        }
    }

    ans.writeln;
}

nebukuro09の日記

AtCoder Regular Contest 081 F - Flip and Rectangles

問題概要

解法

感想

コード (D言語)