SRM 561, Division 1, Level 1 : ICPCBalloons

概要

N 色の風船があり、それぞれの数と大きさ（大小二種類）の情報が与えられる。
この風船を使って（ ICPC のように）正解者に風船を与えるコンテストを開催する。
風船の割り当ては、次の二つの条件を満たさなければならない。

• 同一の問題に対しては、色とサイズが一致しなくてはならない
• 異なる問題に対しては、色が一致してはならない

各問題に大して、正解するチームの最大数が与えられる。
今ある風船では条件を満たしつつ風船を配れるかどうか分からない。
風船の色を変える操作だけができるとき、最小でいくつの風船の色を変えなければならないか答えよ。
どうやっても無理な場合は -1 を返せ。

解法

各問題に対して割り当てるサイズを固定すると、サイズごとに独立に Greedy で計算できます。
サイズの割り当て方を全探索して、内側で 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()
#define PB( n ) push_back( n )

class ICPCBalloons
{
public:
	int calc( VI ac, VI num )
	{
		sort( ALL( ac ), greater<int>() );

		REP( i, 0, min( num.size(), ac.size() ) )
		{
			ac[i] -= num[i];
		}

		int res = 0;

		REP( i, 0, ac.size() )
		{
			if ( ac[i] <= 0 )
			{
				continue;
			}

			res += ac[i];
		}

		return res;
	}

	int solve( VI a, VI b, VI ms, VI ls )
	{
		if ( accumulate( ALL( ms ), 0 ) < accumulate( ALL( a ), 0 ) ||
				accumulate( ALL( ls ), 0 ) < accumulate( ALL( b ), 0 ) )
		{
			return -1;
		}

		return calc( a, ms ) + calc( b, ls );
	}

	int minRepaintings(vector <int> balloonCount, string balloonSize, vector <int> maxAccepted)
	{
		VI ms, ls;

		REP( i, 0, balloonCount.size() )
		{
			if ( balloonSize[i] == 'M' )
			{
				ms.PB( balloonCount[i] );
			}
			else
			{
				ls.PB( balloonCount[i] );
			}
		}

		sort( ALL( ms ), greater<int>() );
		sort( ALL( ls ), greater<int>() );

		const int N = maxAccepted.size();
		int res = INT_MAX;

		REP( flag, 0, 1U << N )
		{
			VI a, b, ac1, ac2;

			REP( i, 0, N )
			{
				if ( flag & ( 1U << i ) )
				{
					a.PB( maxAccepted[i] );
				}
				else
				{
					b.PB( maxAccepted[i] );
				}
			}

			int tmp = solve( a, b, ms, ls );

			if ( tmp < 0 )
			{
				continue;
			}

			res = min( res, tmp );
		}

		return res == INT_MAX ? -1 : res;
	}
};