torus711 のアレ

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

TopCoder, SRM 615, Division 2, Level 1 : AmebaDiv2

問題概要

 アメーバは、自分と同じ大きさのジェルに出会うとそれを吸収して二倍の大きさになる。今、数列 X が与えられる。X の i 項目の要素は、アメーバが i 番目に出会うジェルの大きさである。また、アメーバの初期の大きさは A である。全てのジェルに出会った後のアメーバの大きさを求めよ。

解法

 問題文に記述された通りの手順を実装することで解くことができます。すなわち、X を先頭から走査して、A と等しい値を見つけたら A を A * 2 に更新します。この処理の終了後に残った A の値が答えです。

コード

#define ALL( c ) (c).begin(), (c).end()

class AmebaDiv2
{
public:
	int simulate( vector <int> X, int A )
	{
		return accumulate( ALL( X ), A, []( const int cur, const int x ){ return cur == x ? cur * 2 : cur; } );
	}
};