問題概要
直線上に 個のビルを建てたい.ビルは,端から順に で番号付けられる.ビルの高さには制約があり,その内の 1 つは 要素の 2 つの配列 で説明される.高さの制約は以下のとおりである.
- ビルの高さは非負の整数値をとる
- 1 番のビルの高さは 0 である
- 隣り合うビルの高さの差の絶対値は 1 以下でなければならない
- 番のビルの高さは 以下でなければならない
以上の制約を満たしつつビルを建てたときのビルの高さの最大値を求めよ.
解法
あるビル と,高さが制限されたビル について考えてみます.このとき,ビル の高さは であることが分かります.この計算を高さが制限さればビル全てについて行えば,ビル の高さの最大値を 時間で求めることができます( が定数で抑えられているので).
ビルの数は なので,全てのビルについて,その高さの最大値を求める処理は 時間で実行することができます.定数が大きめですが, はさほど大きくないので問題無く実行できます.
コード
#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; } };