SRM 610 Div1 250 TheMatrix

2014-02-26

14:48 |

最大 100x100 の 1 か 0 が書かれた grid が渡される（プレゼント）。市松模様になってる矩形の面積の最大値を求めよ。

f(始点(x, y), 右方向|下方向, スタートのマス0|1) = その方向に最大何マス市松模様になってるか
を求めたあと、... あれO(N^5)になってしまう
あれんーー
おわり

あとで
y0, y1 を決めた後 x in [0, W] まで見ていきながら y in [y0, y1] が市松模様になってなかったらリセット、なってたらカウンタ++ するなどうまくやると O(N^4)とかO(N^3)とか

それか、まず市松模様状に反転してしまえば矩形内の合計値が w*h か 0 になるかをチェックする問題になる。O(N^4)

accepted in practice room

class TheMatrix {
	public:
	int MaxArea(vector <string> B) {
        int W=B[0].size();
        int H=B.size();
        Sum2D<ll> sum(W, H); // ライブラリ乙
        REP(x, W) REP(y, H) sum.data[y][x] = B[y][x]-'0';
        REP(x, W) REP(y, H) if((x+y)%2) sum.data[y][x]^=1;
        sum.prepare();
        int ans = 0;
        REP(x, W) REP(y, H) RANGE(x2, x, W) RANGE(y2, y, H) {
            int w = x2-x+1;
            int h = y2-y+1;
            ll s = sum.sum(x, y, x2+1, y2+1);
            if(s==0 || s==w*h) ans=max(ans, w*h);
        }
        return ans;
	}
};