TopCoder SRM 609, Division 2, Level 2 : PackingBallsDiv2

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12995&rd=15842

問題概要

　赤、緑、青のボールがそれぞれ R, G, B 個ある。このボールをいくつかの「パッケージ」に分割したい。各パッケージは 1 〜 3 個のボールを含み、加えて次の条件のいずれかを満たす。

• normal set である : 含まれるボールの色が単一
• variety set である : 同じ色のボールを含まない

　最小でいくつのパッケージに分割できるか、求めよ。

解法

　例えば variety set の数が決まっている場合、variety set を構成する段階ではできるだけ多くのボールをパッケージに入れた方が得になります。すなわち、あるパッケージを構成しているとき、ボールが残っている色であればそのパッケージに入れてしまった方が、残りのボールが減るため得になります。variety set を構成し終わった後、残ったボールを normal set となるパッケージに入れることになりますが、この時もできるだけ多くのボールをパッケージに入れていった方が、構成されるパッケージの数を少なくできます。
　制約より、どのボールも 100 個以下しかないので、variety set をいくつ作るか全て試すことができます。variety set の数を仮定できれば、上記の手順で最小となる normal set の数を求められます。こうして求まる解候補の内、最小のものを return すればよいです。

コード

typedef vector<int> VI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( v, c ) for ( auto &v : c )

class PackingBallsDiv2
{
public:
	int minPacks( int R, int G, int B )
	{
		int res = INT_MAX;

		REP( i, 0, 101 )
		{
			VI balls{ R, G, B };

			int cnt = 0;
			FOR( b, balls )
			{
				b = max( 0, b - i );
				cnt += ( b + 2 ) / 3;
			}

			res = min( res, i + cnt );
		}

		return res;
	}
};