TopCoder SRM 582, Division 1, Level 1 : SpaceWarDiv1

問題文

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

概要

N 人の魔法少女がいて、それぞれの強さの情報が与えられる。
また、敵について、「ある強さの敵が何体いるか」という形式で情報が与えられる。
魔法少女は、敵の強さ以上の強さを持っているとき、その敵を倒すことができる。
敵には必ず一人で挑み、敵を一体倒すと疲労が 1 増える。
すべての敵を倒すとき、最も疲労が溜まった魔法少女の疲労の最小値を求めよ。
全て倒すことが不可能な場合は -1 で示せ。

解法

許容される最大の疲労値について二分探索をすると答えが求まります。

ある制約下で敵を全て倒すことができるかどうかの判定方法を考えます。
ある魔法少女とある敵のまとまりについて、その魔法少女が戦える回数と敵の数の小さい方だけ、その魔法少女は敵を倒せます。
この処理を適切な順序で処理することで全て倒せるかどうかの判定が可能で、その順序とは魔法少女・敵ともに強さの降順です。
強さの降順に処理するとき、ある魔法少女以降の魔法少女が倒せる敵の集合は、必ず基準となった魔法少女が倒せる集合の部分集合になります。
選択肢が増えることがないので、この順序で最適な割り当てができそうということになります。
（厳密に証明できていないのです……）

コード

typedef long long LL;
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()

#define PB( n ) push_back( n )
#define MP( a, b ) make_pair( ( a ), ( b ) )

#define fst first
#define snd second

class SpaceWarDiv1
{
public:
	int N, M;
	VI girls;
	vector< pair<LL,LL> > enemies;

	long long minimalFatigue( vector <int> magicalGirlStrength, vector <int> enemyStrength, vector<long long> enemyCount )
	{
		if ( find_if( ALL( enemyStrength ), bind1st( less<int>(), *max_element( ALL( magicalGirlStrength ) ) ) ) != enemyStrength.end() )
		{
			return -1;
		}

		N = magicalGirlStrength.size();
		M = enemyStrength.size();

		girls = magicalGirlStrength;
		sort( ALL( girls ), greater<int>() );
		REP( i, 0, enemyStrength.size() )
		{
			enemies.PB( MP( enemyStrength[i], enemyCount[i] ) );
		}
		sort( ALL( enemies ), greater< pair<LL,LL> >() );

		LL lb = 0, ub = accumulate( ALL( enemyCount ), 0LL );
		while ( lb + 1 < ub )
		{
			LL mid = ( lb + ub ) / 2;
			if ( check( mid ) )
			{
				ub = mid;
			}
			else
			{
				lb = mid;
			}
		}

		return ub;
	}

	bool check( LL f )
	{
		int j = 0;
		vector<LL> fs( N, f );
		vector< pair<LL,LL> > e( enemies );

		REP( i, 0, N )
		{
			while ( j < M && ( e[j].snd == 0 || girls[i] < e[j].fst ) )
			{
				j++;
			}

			if ( M <= j )
			{
				break;
			}
			const LL num = min( e[j].snd, fs[i] );
			e[j].snd -= num;
			fs[i] -= num;
			if ( fs[i] )
			{
				i--;
			}
		}

		REP( i, 0, M )
		{
			if ( e[i].snd != 0 )
			{
				return false;
			}
		}
		return true;
	}
};