読者です 読者をやめる 読者になる 読者になる

torus711 のアレ

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

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

問題概要

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

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

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

解法

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

コード

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;
	}
};