TopCoder, Single Round Match 645, Division 2, Level 1 : BacteriesColony

問題文

　http://community.topcoder.com/stat?c=problem_statement&pm=13604&rd=16277

問題概要

　バクテリアの入った容器が一列に並べられている．このバクテリアは，日中に於ける両隣の容器のバクテリアの量によって，夜間に増減する（変化しない場合もある）．バクテリアの数が変化する条件は 2 通りで，着目している容器から見て，

• 両隣の容器の中のバクテリアが，共に着目している容器のそれより多い → 容器内のバクテリアが単位量増える
• 両隣の容器の中のバクテリアが，共に着目している容器のそれより少ない → 容器内のバクテリアが単位量減る

である．一番端に配置された容器内のバクテリアの数は変化しない．
　並べられた容器内のバクテリアの量の情報が与えられる．この容器群を，量が変化しなくなるまで放置する．各容器について，最終的なバクテリアの量を求めよ．
　バクテリアの量に関する情報は配列 で与えられ，各 について が端から 番目の容器の中にいるバクテリアの量を表す．
　
　

解法

　 と書きます．
　まず，状態変化のルールが与えられているので，これをそのままシミュレーションすることで答えを計算できるような気持ちになります．ここで気になるのは，このシミュレーションの実行に掛かる時間です．それを知るためには，状態変化が何回起こり得るかを知らなければなりません．
　端ではない 1 つの容器について考えます．その両側の容器の内容量が変化しないとすると，この容器の内容量が変化する回数は高々 99 回です．これは，両側または自身のいずれかの内容量が 1 で，他方が 100 の場合です．他のどのような場合を考えてみても，100 回以上変化することはできません．更に，両側の容器の内容量が変化するとすれば，変化ルールより，自身の内容量に近づく方向への変化に限られます．従って，両側の内容量変化によって変化回数が増えることもありません．このことが全ての容器について言えるので，全体でも変化の回数は高々 99 回です．1 回の変化に於ける各容器の内容量の変化量は，各容器に対して 2 個の容器の内容量を調べることで計算できるので，全て計算しても で求まります．変化分の適用も同じオーダーでできるので，変化 1 回あたりのシミュレーションは でできます． の上限と，変化の起こる回数の上限から，愚直にシミュレーションをしても間に合いそうであることが分かります．

コード

using VI = vector< int >;

#define REP( i, m, n ) for ( int i = ( int )( m ); i < ( int )( n ); ++i )
#define ALL( c ) ( c ).begin(), ( c ).end()

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

class BacteriesColony
{
public:
	vector <int> performTheExperiment( vector <int> colonies )
	{
		const int N = SZ( colonies );

		REP( iteration, 0, 100 )
		{
			VI dx( N );
			REP( i, 1, N - 1 )
			{
				if ( colonies[ i - 1 ] < colonies[i] && colonies[i] > colonies[ i + 1 ] )
				{
					dx[i] = -1;
				}
				if ( colonies[ i - 1 ] > colonies[i] && colonies[i] < colonies[ i + 1 ] )
				{
					dx[i] = +1;
				}
			}
			transform( ALL( colonies ), dx.begin(), colonies.begin(), plus< int >() );
		}
		return colonies;
	}
};