TopCoder SRM 573, Division 2, Level 2 : TeamContestEasy

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12471&rd=15493

概要

基本的に Div1, Level 1 と同一。
ただしこちらは、チームの強さは強い方二人の強さの合計。

解法

あるチームに於いて、最強の人を決めると、そのチームが自チームより強くなるために必要な、二番目に強い人の強さが求まります。
三人目については、できるだけ強い人を残すように選択するのが後の選択に於いて強いチームを作りやすくなるので、残った人のうちで最も弱い人を選びます。

コード

typedef vector<int> VI;

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

class TeamContestEasy
{
public:
	int worstRank( vector <int> strength )
	{
		if ( strength.size() == 3 )
		{
			return 1;
		}

		const int own = accumulate( strength.begin(), strength.begin() + 3, 0 ) - *min_element( strength.begin(), strength.begin() + 3 );
		VI rest( strength.begin() + 3, strength.end() );
		sort( ALL( rest ), greater<int>() );

		int res = 1;

		while ( true )
		{
			const int N = rest.size();
			int str = rest[0], found = -1;
			for ( int i = N - 1; 1 <= i; i-- )
			{
				if ( own < str + rest[i] )
				{
					found = i;
					break;
				}
			}

			if ( found == -1 )
			{
				break;
			}

			rest.erase( rest.begin() + found );
			rest.erase( rest.begin() );

			if ( !rest.empty() )
			{
				rest.pop_back();
				res++;
			}
			else
			{
				break;
			}
		}

		return res;
	}
};