F - Flip and Rectangles

Submission #4195664 - AtCoder Regular Contest 081

2*2の時について考えると
黒の合計が偶数の時のみ全てを黒くできるとわかる
また、この領域からなる長方形も全て黒くできる

なぜなら、どのような操作をしても2*2正方形内の黒は偶数個あり
左端と上を黒くした際に全てが黒くなるからである

よって正方形の座標を圧縮すれば最大正方形問題に帰着できる
Submission #4195664 - AtCoder Regular Contest 081

void solve(int n_, vi a_) {
    cin >> H >> W;
    nt(C, H, W);
    S = ctoi(C, '#');
    ma = max(H,W);
    //左上に置く
    rep(h, H) {
        rep(w, W) {
            if (h < H - 1 && w < W - 1) {
                his[h][w] = (S[h][w] + S[h + 1][w] + S[h][w + 1] + S[h + 1][w + 1]) % 2 == 0;
            }
        }
    }
    rep(h, H) {
        rep(w, W) {
            if (h && his[h][w])his[h][w] += his[h - 1][w];
        }
        vp st;
        rep(w, W) {
            int j = w;
            while (s(st) && st.back().S > his[h][w]) {
                P b = st.back();
                int nw = w - b.F;
                int nh = b.S;
                chmax(ma, (nh + 1) * (nw + 1));
                j = b.F;
                st.pop_back();
            }
            st.eb(j, his[h][w]);
        }
    }
    cout << ma << endl;
}