TopCoder, SRM 623, Division 1, Level 1 : UniformBoard

問題文

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

問題概要

　 のグリッド状の盤面があり、各グリッドは、丁度一つのりんごか梨のいずれかがあるか、空であるかのいずれかである。この盤面に対し、一つのフルーツを選んで空いているグリッドに移動する操作を K 回までできる。
　盤面上の矩形領域であって、内部のグリッド全てにりんごが置かれているようなものを uniform であると呼ぶ。K 回以内の操作で作ることができる uniform な矩形領域であって、面積が最大となるものの面積を求めよ。
　N <= 20

解法

　N <= 20 とまぁまぁ小さいので、矩形領域を全て試すことができます。従って問題は、ある矩形領域を決めたときにその部分を uniform にするための最小手数（あるいは不可能であるか）を求める部分問題に帰着されます。
　着目している矩形領域の面積を area 、領域内のりんごの数を a 、梨の数を p と置きます。領域外部に空グリッドが一つでもあれば、そこを利用して領域内の梨と了以9期外のりんごを二手で交換できます。また、領域内部に空グリッドが存在して、領域外部にりんごがあったとすれば、その空グリッドは外部のりんごによって必ず埋められるので、この操作は無条件に実行してよいことなります。このことを踏まえると最適な手順は、

1. 領域外部のりんごで領域内部の空グリッドを埋める。m = min( りんごの総数 - a, area - a - p ) とすると a += p と変化する。かかる手数は m 。
2. 領域外部に秋グリッドが存在すれば、それを利用して領域内部の梨と外部のりんごを交換する。m = min( りんごの総数 - a, p ) とすると、a += p と変化する。かかる手数は 2m 。

となります。この手順が終わった後、area = a ならば、着目している矩形は uniform に変化したと言えるので、解を更新します。この手順を全ての矩形領域に対して施すことで、全体の最適解を得ることができます。

コード

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

// 累積和による区間 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 UniformBoard
{
public:
	int getBoard(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 );
						int a = csum_a.sum( y1, x1, y2, x2 );
						int p = csum_p.sum( y1, x1, y2, x2 );
						int e = area - a - p;

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

						if ( a == area && steps <= K )
						{
							res = max( res, area );
						}
					}
				}
			}
		}

		return res;
	}
};