TopCoder SRM 573, Division 1, Level 1 : TeamContest

問題文

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

概要

0 から N * 3 - 1 に番号付けされた N * 3 人が三人で一つのチームを組みプログラミングコンテストに参加する。
参加者の強さは配列 strength にて与えられ、チームの強さは、チーム内の最強の人と最弱の人の strength を足した値となる。
自分のチームは 0 から 2 番の参加者である場合、自分のチームは最悪何番目の強さになるか求めよ。

解法

相手のチームに於ける最強の人を決めると、そのチームが自チームに勝つために必要な最弱の人の強さが決まります。
三人目は、最強の人以下且つ最弱の人以上の強さの人の中から選ぶことになりますが、強い人を残すようにすると、後の選択で自チームに勝つチームの数を最大にできます。
従って、三人目は最弱の人以上の強さをもつ人の中で最弱の人となります。
予めソートしておいて、チームに於ける最強の人を Greedy に選び、条件を充足する最弱の人と組ませていけばよいです。

コード

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 TeamContest
{
public:
	int worstRank( vector <int> strength )
	{
		int own = *min_element( strength.begin(), strength.begin() + 3 ) + *max_element( strength.begin(), strength.begin() + 3 );
		VI rest( strength.begin() + 3, strength.end() );

		int res = 1;
		sort( ALL( rest ), greater<int>() );
		REP( i, 0, rest.size() )
		{
			int found = -1;
			REP( j, i + 1, rest.size() - 1 )
			{
				if ( rest[i] + rest[ j + 1 ] <= own )
				{
					break;
				}
				found = j;
			}

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

			res++;
			rest.erase( rest.begin() + found, rest.begin() + found + 2 );
		}
		
		return res;
	}
};