TopCoder SRM 582, Division 2, Level 2 : SpaceWarDiv2

解法

http://community.topcoder.com/stat?c=problem_statement&pm=12605&rd=15502

概要

制約以外 Division 1, Level 1 と同一。

解法

Division 1, Level 1 と同様の二分探索でももちろん解けますが……

昨日の Div2-2 と Div1-1 、制約違うけど Div-2 の制約の緩さを利用できる解法ってあるのかな……。32bit 整数に収まることぐらいしか利点無いように思えてならない

2013-06-15 23:14:52 via Janetter

@torus711 敵を一匹ずつ扱って、一番つらみが低い魔法少女に倒させるとかどうですか

2013-06-15 23:17:14 via mikutter to @torus711

ということで Greedy でも解けます。（ takapt さんありがとうございました）

より詳細に言うと次のようになります。
まず、敵を一体毎に分解して強さを並べた配列を作り、それを降順ソートします。
そうすると、i 番目の敵を倒せる魔法少女の内で最も疲労度が低い魔法少女がその敵を倒すようにすれば最適な割り当てが求まります。
着目している敵を倒せる魔法少女の数は増加するので疲労度は均等に分配され、最大値が最小化されます。

コード

typedef vector<int> VI;
typedef pair<int,int> PII;

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

class SpaceWarDiv2
{
public:
	int minimalFatigue( vector <int> magicalGirlStrength, vector <int> enemyStrength, vector <int> enemyCount )
	{
		VI enemies;
		REP( i, 0, enemyStrength.size() )
		{
			REP( j, 0, enemyCount[i] )
			{
				enemies.PB( enemyStrength[i] );
			}
		}

		sort( ALL( magicalGirlStrength ), greater<int>() );
		sort( ALL( enemies ), greater<int>() );

		const int N = magicalGirlStrength.size(), M = enemies.size();
		VI tsurami( N, 0 );


		REP( im, 0, M )
		{
			int will = -1;
			REP( in, 0, N )
			{
				if ( enemies[ im ] <= magicalGirlStrength[ in ] && ( will == -1 || tsurami[ in ] < tsurami[ will ] ) )
				{
					will = in;
				}
			}

			if ( will == -1 )
			{
				return -1;
			}

			tsurami[ will ] ++;
		}

		return *max_element( ALL( tsurami ) );
	}
};