Flip and Rectangles [AtCoder Regular Contest 081 F]

https://beta.atcoder.jp/contests/arc081/tasks/arc081_d

前提知識

• 最大長方形

解法

https://beta.atcoder.jp/contests/arc081/submissions/1530633

この問題の難しい所は2つある。
もし最大長方形問題に初めて会うのであれば、最大長方形について演習してから、この問題に取り組むといいだろう。

1. 条件の言い換え
2. 最大長方形の計算

まず1番目であるが、これは公式解説放送を見るのが分かりやすいが「2*2の正方形において黒の個数%2==0であれば全て黒にできる」という感じに条件を言い換えられる。
その為、(W-1)*(H-1)の配列を別途用意し、黒の個数%2==0なら0, 黒の個数%2==1なら1として配列を作る。
要するにパリティ(偶奇)を計算していることになるので、これはxorを使えばいい（使わなくても何でもいい）。
　
次は最大長方形の計算方法であるが、stackを用いた有名な計算方法がある。
自分の解法では実装をサボってtuboさんのライブラリをそのまま使ったが、アイデアは分かりやすい。
stack内で単調増加を保ちながら更新していく感じで、dequeを使って単調的に更新していくアレと似ている気がする。

int H, W;
string S[2020];
int A[2020][2020];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W; rep(y, 0, H) cin >> S[y];
    rep(y, 0, H) rep(x, 0, W) {
        if (S[y][x] == '#') A[y][x] = 1;
        else A[y][x] = 0;
    }
 
    vector<vector<int>> v(H - 1, vector<int>(W - 1, 0));
    rep(y, 0, H - 1) rep(x, 0, W - 1) v[y][x] = A[y][x] ^ A[y + 1][x] ^ A[y][x + 1] ^ A[y + 1][x + 1];
    ll ans = maxRectangle(v);
    ans = max(ans, (ll)max(H, W));
    cout << ans << endl;
}