torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

TopCoder, SRM 636, Division 1, Level 1 : ChocolateDividingEasy

問題概要

 グリッド状の盤面があり、各セルには得点が割り振られている。得点は文字列配列 C で表され、盤面の i 行目 j 列目のセルの得点は C_{ij} である。
 この盤面を、いずれも空でなく辺が行または列に平行な 9 つの長方形領域に分割する。正確には、異なる行間を 2 箇所、異なる列間を 2 箇所選んで、選ばれた線をまたいで接するセル同士は異なる領域に属するとする。
 分割操作後の各領域について、領域に含まれるセルの得点の合計を領域の得点とする。最も得点の低い領域の得点を最大化したとき、その得点を求めよ。

解法

 与えられる盤面の高さと幅をそれぞれ H, W と書きます。
 分割の方法は O( H^2 W^2 ) あります。予め盤面の(二次元)累積和をとっておけば、長方形領域の要素の合計を定数時間で計算できるので、ある分割に於ける得点の最低値も定数時間で計算できます。累積和をとってから分割のしかたを全通り試せば、O( H^2 W^2 ) 時間で答えを求めることができます。

コード

using VI = vector<int>; using VVI = vector<VI>;
template < typename T = int > using LIM = numeric_limits<T>;

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

// 累積和による区間 Sum クエリ
// 前処理 O( HW )
// クエリ O( 1 )
class ConsecutiveSums2d
{
private:
	const int H, W;
	vector< vector< long long > > src, csum;
	bool isSolved = false;

public:
	ConsecutiveSums2d( const int h, const int w ) : H( h ), W( w ), src( H, vector< long long >( W ) ) {}
	ConsecutiveSums2d( const vector< vector< long long > > &s ) : H( s.size() ), W( s[0].size() ), src( s ) {}
	ConsecutiveSums2d( const vector< vector< int > > &s ) : H( s.size() ), W( s[0].size() ), src( H, vector< long long >( W, 0 ) )
	{
		for ( int i = 0; i < H; ++i )
		{
			for ( int j = 0; j < W; ++ j )
			{
				src[i][j] = s[i][j];
			}
		}
		return;
	}


	ConsecutiveSums2d( const vector< string > &s ) : H( s.size() ), W( s[0].size() ), src( H, vector< long long >( W, 0 ) )
	{
		for ( int i = 0; i < H; ++i )
		{
			for ( int j = 0; j < W; ++ j )
			{
				src[i][j] = s[i][j] - '0';
			}
		}
		return;
	}

	int get( const int y, const int x ) const
	{
		return src[y][x];
	}

	void set( const int y, const int x, const long long v )
	{
		src[y][x] = v;
		isSolved = false;
		
		return;
	}

	long long sum( const int y1, const int x1, const int y2, const int x2 )
	{
		if ( !isSolved )
		{
			solve();
		}
		return csum[ y2 + 1 ][ x2 + 1 ] - csum[ y2 + 1 ][ x1 ] - csum[ y1 ][ x2 + 1 ] + csum[ y1 ][ x1 ];
	}

private:
	void solve()
	{
		csum.clear();
		csum.resize( H + 1, vector< long long >( W + 1 ) );

		for ( int i = 0; i < H; ++i )
		{
			partial_sum( src[i].begin(), src[i].end(), csum[ i + 1 ].begin() + 1 );
		}

		for ( int i = 0; i < H; ++i )
		{
			for ( int j = 0; j <= W; ++j )
			{
				csum[ i + 1 ][j] += csum[i][j];
			}
		}

		isSolved = true;
		return;
	}
};
// Consecutivesums2d( H, W )
// Consecutivesums2d( SRC )
// get( y, x )
// set( y, x, value )
// sum( y1, x1, y2, x2 )

class ChocolateDividingEasy
{
public:
	int findBest( vector <string> chocolate )
	{
		const int H = chocolate.size(), W = chocolate[0].size();

		ConsecutiveSums2d csums( chocolate );

		int res = 0;
		REP( y1, 1, H )
		{
			REP( y2, y1 + 1, H )
			{
				REP( x1, 1, W )
				{
					REP( x2, x1 + 1, W )
					{
						const VI ys( { 0, y1, y2, H } );
						const VI xs( { 0, x1, x2, W } );

						int tmp = LIM<>::max();
						REP( i, 0, 3 )
						{
							REP( j, 0, 3 )
							{
								tmp = min<int>( tmp, csums.sum( ys[i], xs[j], ys[ i + 1 ] - 1, xs[ j + 1 ] - 1 ) );
							}
						}
						res = max( res, tmp );
					}
				}
			}
		}

		return res;
	}
};