TopCoder SRM 605 Div2 Medium AlienAndGame

あまり難しくない。
http://community.topcoder.com/stat?c=problem_statement&pm=12821

問題

長方形(H x W)のグリッドの各セルに対し、白黒が割り当てられている。
プレイヤーはいくつか行を選択し、白と黒を反転させることができる。
その結果得られる、白のみまたは黒のみのセルで構成された最大の正方形の面積を求めよ。

解法

白黒反転の条件がなければ、単に正方形の探索を行う典型問題。

白黒の条件を考えると、各行N個のセルの色が連続しているような連続するN行を探せばよい。
行同士で色は一致する必要はない。

まず、各行を見て各セルから右側何個同じ色のセルが続くかカウントする。
次に、NxNの正方形が作れるか見るため、各セルから下方向N個たどったとき、それぞれ右側N個が同じかどうかチェックすればよい。
O(HW)でも処理できるが、ここでは面倒なのでO(H^2 W^2)で横着なコードを書いている。

class AlienAndGame {
	int same[51][51];
	public:
	int getNumber(vector <string> board) {
		int H=board.size(),W=board[0].size();
		int y,x,w,l=1;
		ZERO(same);
		FOR(y,H) {
			for(x=W-1;x>=0;x--) {
				if(x<W-1 && board[y][x]==board[y][x+1]) same[y][x]=same[y][x+1];
				same[y][x]++;
			}
		}
		FOR(y,H) FOR(x,W) {
			for(w=1;x+w<=W;w++) {
				int ng=0;
				if(y+w>H) break;
				for(int y2=y;y2<y+w;y2++) if(same[y2][x]<w) ng++;
				
				if(ng) break;
				l=max(l,w);
			}
		}
		return l*l;
	}
};

まとめ

まじめに計算量落とせばよかったかな。