TopCoder SRM 579, Division 2, Level 1 : PrimalUnlicensedCreatures

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12524&rd=15499

概要

モンスターを他のモンスターと戦わせる。
自分のモンスターの強さが相手のそれより厳密に高いとき、自分のモンスターが勝つことができる。
相手のモンスターに勝ったとき、相手の強さ / 2 ( 余り切り捨て ) だけ、自分のモンスターの強さが上がる。
自分のモンスターの強さと、相手に選ぶことができるモンスターの強さの情報が与えられる。
最大で何体のモンスターを倒すことができるか求めよ。

解法

あるモンスターに挑むとき、それより弱いモンスターを全て倒しても勝てないならば、そのモンスターを倒すことはできません。
従って、すべてのモンスターについてこの条件を成立させながら勝敗を見ていけばよいことになります。
そのような挑み方の順序は強さの昇順であるので、予めソートしてシミュレーションすれば解けます。

コード

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

class PrimalUnlicensedCreatures
{
public:
	int maxWins( int initialLevel, vector <int> grezPower )
	{
		sort( ALL( grezPower ) );

		int cur = initialLevel, res = 0;
		REP( i, 0, grezPower.size() )
		{
			if ( grezPower[i] < cur )
			{
				cur += grezPower[i] / 2;
				res++;
			}
		}
		return res;
	}
}