TopCoder SRM 610 Div1 Easy TheMatrix

SRM610は不参加。後で復習したらEasyで入力サイズを見誤ってミス、Mediumは解けていたのでレートは出ても出なくてもほとんど変化なかった。
http://community.topcoder.com/stat?c=problem_statement&pm=13035

問題

２次元グリッド上の各セルが白黒に塗られている。
このうち、市松模様になっている最大面積の長方形を求めよ。

解法

市松模様でなく、最大面積の単色長方形ならよくある問題だね。
アプローチとしてはほぼ同様にとける。

まず各行で左端から右方向にセルを見て行って、各セルの左側に何マス市松模様状に交互に白黒マスが並ぶか数える。

次に、長方形の各セルを右上とする長方形を求めていく。
長方形の各セルから下方向にやはり市松模様状にセルをたどっていき、そこを右下とする長方形を求める。
各セルから左方向に何マス市松模様が続くかわかるので、右上のセルと右下のセルの位置から高さがわかり、その間のセルが左方向に続く市松模様状のセルの最小値が幅がわかる。
O(N^3)なのでN<=100でも間に合う。

int ma[101][101];

class TheMatrix {
	int R,C;
	public:
	int MaxArea(vector <string> board) {
		int y,x,h;
		R=board.size();
		C=board[0].size();
		ZERO(ma);
		
		FOR(y,R) FOR(x,C) {
			if(x==0 || board[y][x]==board[y][x-1]) ma[y][x]=1;
			else ma[y][x]=ma[y][x-1]+1;
		}
		
		int mama=0;
		FOR(x,C) FOR(y,R) {
			int mi=ma[y][x];
			for(h=1;h+y<=R;h++) {
				if(h>1 && board[y+h-1][x]==board[y+h-2][x]) break;
				mi=min(mi,ma[y+h-1][x]);
				mama=max(mama,h*mi);
			}
		}
		return mama;
	}
}

まとめ

そういえば入力サイズが増えて100x100の文字列配列が可能になったんだな…。
最初50x50で解いてSegFault起きてびっくりした。