torus711 のアレ

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

TopCoder SRM 582, Division 2, Level 2 : SpaceWarDiv2

概要

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

解法

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

ということで 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 ) );
	}
};