torus711 のアレ

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

TopCoder SRM 595, Division 2, Level 1 : LittleElephantAndBallsAgain

概要

三色のボールが一列に並んでいる。
次の操作を繰り返し適用して、列中の色の種類を一つにしたい。

  • 左右いずれかの端のボールを取り除く

目標を達成するまでの操作回数の最小値を求めよ。

解法

最後に残す範囲を全通り試すことができます。
残す範囲が単一色であれば、その左右にあるボールの数で答えを更新していきます。
範囲が単一色かどうかは、その範囲を元に set のテンポラリオブジェクトを作って、サイズが 1 かどうかをみればよいです。

コード

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

class LittleElephantAndBallsAgain
{
public:
	int getNumber( string S )
	{
		const int N = S.size();

		int res = INT_MAX;
		REP( i, 0, N )
		{
			REP( j, i + 1, N + 1 )
			{
				if ( set<char>( S.begin() + i, S.begin() + j ).size() == 1 )
				{
					res = min( res, i + ( N - j ) );
				}
			}
		}
		return res;
	}
};