torus711 のアレ

主に競技プログラミングの問題について書きます

TopCoder, Single Round Match 647, Division 1, Level 1 : BuildingTowersEasy

問題概要

 直線上に N 個のビルを建てたい.ビルは,端から順に 1, 2, \dots, N で番号付けられる.ビルの高さには制約があり,その内の 1 つは \min( N, 50 ) 要素の 2 つの配列 x, t で説明される.高さの制約は以下のとおりである.

  • ビルの高さは非負の整数値をとる
  • 1 番のビルの高さは 0 である
  • 隣り合うビルの高さの差の絶対値は 1 以下でなければならない
  • x_i 番のビルの高さは t_i 以下でなければならない

 以上の制約を満たしつつビルを建てたときのビルの高さの最大値を求めよ.
 N \leq 10^5

解法

 あるビル i と,高さが制限されたビル j について考えてみます.このとき,ビル i の高さは \min( i - 1, t_j + | x_i - i | ) であることが分かります.この計算を高さが制限さればビル全てについて行えば,ビル i の高さの最大値を O( 1 ) 時間で求めることができます( |x| が定数で抑えられているので).
 ビルの数は O( N ) なので,全てのビルについて,その高さの最大値を求める処理は O( N ) 時間で実行することができます.定数が大きめですが,50 \times 10^5 はさほど大きくないので問題無く実行できます.

コード

#define REP2( i, n ) for ( int i = 0; i < ( int )( n ); ++i )
#define REP3( i, m, n ) for ( int i = ( int )( m ); i < ( int )( n ); ++i )
#define GET_REP( a, b, c, F, ... ) F
#define REP( ... ) GET_REP( __VA_ARGS__, REP3, REP2 )( __VA_ARGS__ )
#define ALL( c ) ( c ).begin(), ( c ).end()

#define SZ( v ) ( (int)( v ).size() )

class BuildingTowersEasy
{
public:
	int maxHeight( int N, vector <int> x, vector <int> t )
	{
		transform( ALL( x ), x.begin(), bind( minus< int >(), _1, 1 ) );

		int res = 0;
		REP( i, N )
		{
			int tmp = i;
			REP( j, SZ( x ) )
			{
				tmp = min( tmp, t[j] + abs( x[j] - i ) );
			}
			res = max( res, tmp );
		}
		return res;
	}
};