TopCoder, SRM 623, Division 2, Level 3 : ApplesAndPears

問題文

　http://community.topcoder.com/stat?c=problem_statement&pm=12935&rd=15856

問題概要

　Division 1, Level 1 とほぼ同一。ただし、uniform であることの要件は、矩形領域内部のグリッドが全て同一の状態であること。
　N <= 50

解法

　りんごによる uniform な領域に関しては Division 1, Level 1 と完全に同一です。また梨による uniform な領域も、りんごと梨を入れ替えれば同じ手順で求めることができます。残りは空グリッドによる uniform な領域ですが、これは単純に仮定した領域内部にある果物を全て外に出せば良いので、（内部の果物の数）≦（外部の空グリッドの数）　のとき、内部の果物の数と等しい手数で構築できます。あとは、Division 1, Level 1 と同様に矩形領域を全て試すことで、問題を解くことができます。
　なお、こちらの Edition では N の成約が 50 以下になっているので、数を数えるのに累積和を使わない（ ）と TLE してしまいます。

コード

using PII = pair<int,int>;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

#define MP( a, b ) make_pair( ( a ), ( b ) )

#define fst first
#define snd second

// 累積和による区間 Sum クエリ
// 前処理 O( HW )
// クエリ O( 1 )
class ConsecutiveSums2d;
// Consecutivesums2d( H, W )
// Consecutivesums2d( SRC )
// get( y, x )
// set( y, x, value )
// sum( y1, x1, y2, x2 )

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

		ConsecutiveSums2d csum_a( H, W ), csum_p( H, W );
		map<char,int> counts;
		REP( i, 0, H )
		{
			REP( j, 0, W )
			{
				if ( board[i][j] == 'A' )
				{
					csum_a.set( i, j, 1 );
				}
				if ( board[i][j] == 'P' )
				{
					csum_p.set( i, j, 1 );
				}

				counts[ board[i][j] ]++;
			}
		}

		int res = 0;
		REP( y1, 0, H )
		{
			REP( y2, y1, H )
			{
				REP( x1, 0, W )
				{
					REP( x2, x1, W )
					{
						const int area = ( y2 - y1 + 1 ) * ( x2 - x1 + 1 );
						const int a = csum_a.sum( y1, x1, y2, x2 );
						const int p = csum_p.sum( y1, x1, y2, x2 );
						const int e = area - a - p;
						
						{
							const PII tmp = packing( counts, 'A', a, p, e );
							if ( tmp.fst == area && tmp.snd <= K )
							{
								res = max( res, area );
							}
						}
						{
							const PII tmp = packing( counts, 'P', p, a, e );
							if ( tmp.fst == area && tmp.snd <= K )
							{
								res = max( res, area );
							}
						}
						{
							if ( area <= counts[ '.' ] && area - e <= K )
							{
								res = max( res, area );
							}
						}
					}
				}
			}
		}

		return res;
	}

	PII packing( map<char,int> &counts, const char ch, int a, int p, int e )
	{
		int steps = 0;
		{ // apple を中に入れる : これで外部に空きができる
			const int num = min( counts[ ch ] - a, e );
			a += num;
			e -= num;
			steps += num;
		}
		if ( counts[ '.' ] - e )
		{  // 外部の空きを利用して外部の apple を内部の pear とスワップ
			const int num = min( counts[ ch ] - a, p );
			a += num;
			p -= num;
			steps += 2 * num;
		}

		return MP( a, steps );
	}
};