TopCoder SRM 605, Division 2, Level 2 : AlienAndGame

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12821&rd=15838

問題概要

　グリッド状の盤面があり、各セルは黒か白で塗られている。盤面の情報は文字列の配列で与えられ、'B' が黒、'W' が白のセルを表す。
　一つの行を選んで、その行の全てのセルの色を反転させる操作を任意回できる。作ることができる白い正方形の最大面積を求めよ。

解法

　正方形を作る領域を先に決めるとします。左上座標とサイズを決めると領域が決まります。そうして決まった領域に正方形を作れるかどうかを判定することができれば、問題を解くことができます。
　操作の特性を考えると、ある行のある範囲内に二種類以上の文字が存在するときに限り、その部分を全て 'W' にすることができません。そうでない場合、その部分を全て 'W' にすることが可能です。従って、予め決めた領域に含まれる行の内、その領域に含まれる範囲にある部分文字列を一行ずつ取り出して文字の種類を数えることで判定可能となります。
　下のコードの場合、かなりこわいオーダーになってますが 500 ms 弱で通りました。もし本番だったらこれはやりたくないので、どちらかの文字の数を累積和で前計算して判定部分を高速化するのがよいと思いました。

コード

class AlienAndGame
{
public:
	int getNumber( vector <string> board )
	{
		const int H = board.size(), W = board[0].size();

		int res = 0;
		REP( x1, 0, W )
		{
			REP( y1, 0, H )
			{
				REP( n, 0, 50 )
				{
					const int x2 = x1 + n, y2 = y1 + n;
					if ( H <= y2 || W <= x2 )
					{
						continue;
					}

					bool ok = true;
					REP( y, y1, y2 + 1 )
					{
						const string s = board[y].substr( x1, x2 - x1 + 1 );
						ok &= set<char>( ALL( s ) ).size() == 1;
					}
					if ( ok ) res = max( res, ( n + 1 ) * ( n + 1 ) );
				}
			}
		}

		return res;
	}
};