TopCoder SRM 568, Divison 1, Level 1 : BallsSeparating

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12398&rd=15488

概要

N 個の箱に、三色のボールがいくつか入っている。
一回の操作で、一つのボールを他の箱に移動することができる。
このとき、全ての箱の中身を単一色にするために必要な操作回数の最小値を求めよ。
そのような状態にすることが不可能な場合は -1 を返せ。

解法

制約より、どの色のボールも一つ以上存在します。
従って、N < 3 のときは -1 となります。

次に、ボールの移動について考えます。
この部分を計算する方法は二つあります。
どちらの方針でも共通する前提は、どの箱についても、二色のボールを全て移動することで中身を単一色にすることができるという点です。
（あとの一色を別の箱にマージすることは無駄です）
また、移動先については考慮する必要が無く、各色について少なくとも一つの箱が割り当てられていれば大丈夫です。

1. Brute Force

基本的には、各箱について最も多い色を残し、その他の色を全て他の箱に移動することで手順を最小化できます。
ただし、それだけでは箱が割り当てられない色（＝行き場の無くなる色）が発生します。
そこで、各色について、一つの箱を強制的に割り当て、その他の箱は多い色を残すようにします。
強制的な割り当てのパターンが N^3 、手数の計算が O( N ) なので全体で O( N^4 ) になります。

コード

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

const int INF = INT_MAX / 4;

class BallsSeparating
{
public:
	int minOperations( vector <int> red, vector <int> green, vector <int> blue )
	{
		const int N = red.size();

		if ( N < 3 )
		{
			return -1;
		}

		int res = INF;

		REP( i, 0, N )
		{
			REP( j, 0, N )
			{
				REP( k, 0, N )
				{
					if ( i == j || j == k || k == i )
					{
						continue;
					}

					int tmp = 0;

					REP( t, 0, N )
					{
						if ( t == i )
						{
								tmp += green[t] + blue[t];
						}
						else if ( t == j )
						{
							tmp += red[t] + blue[t];
						}
						else if ( t == k )
						{
							tmp += red[t] + green[t];
						}
						else
						{
							tmp += red[t] + green[t] + blue[t] - max( red[t], max( green[t], blue[t] ) );
						}
					}

					res = min( res, tmp );
				}
			}
		}

		return res;
	}
};

2. 動的計画法

各色に箱を割り当てたかどうかは 3 bit の情報ですので、0 〜 7 の整数にエンコードできます。
この整数と処理した箱の数の二つのパラメータで状態を表すことができ、次のような動的計画法を考えることができます。
dp[ 考慮した箱の数 ][ 色への箱の割り当て状態 ] := この状態への最小手数
この配列を順に更新することで答えが求まります。
なお、dp 配列のデフォルト値は INF, dp[0][0] は 0 で初期化します。
このアルゴリズムのオーダーは O( N * 2^3 ) = O( N ) です。

コード

typedef vector<int> VI;
typedef vector<VI> VVI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

const int INF = INT_MAX / 4;

class BallsSeparating
{
public:
	int minOperations( vector <int> red, vector <int> green, vector <int> blue )
	{
		const int N = red.size();

		if ( N < 3 )
		{
			return -1;
		}

		VVI dp( N + 1, VI( 1 << 3, INF ) );
		dp[0][0] = 0;

		REP( i, 0, N )
		{
			REP( j, 0, 1 << 3 )
			{
				if ( dp[i][j] == INF )
				{
					continue;
				}

				dp[ i + 1 ][ j | 1 ] = min( dp[ i + 1 ][ j | 1 ], dp[i][j] + green[i] + blue[i] );
				dp[ i + 1 ][ j | 2 ] = min( dp[ i + 1 ][ j | 2 ], dp[i][j] + red[i] + blue[i] );
				dp[ i + 1 ][ j | 4 ] = min( dp[ i + 1 ][ j | 4 ], dp[i][j] + red[i] + green[i] );
			}
		}

		return dp.back().back();
	}
};