TopCoder Open, Algorithm、Round 1A, Level 2 : EllysScrabble

問題文

　http://community.topcoder.com/stat?c=problem_statement&pm=12974&rd=15942

問題概要

　文字列 letters と整数 maxDistance が与えられる。letters の各文字について、元の位置との距離が maxDistance を超えない範囲で、letters を並べ替えることができる。構築できる文字列のうち、辞書順最小のものを求めよ。

解法

　手前の値をよくできるならば後ろがどんなに悪くなってもよい、という辞書順最小の定石を使い、先頭から順に可能な限り小さな文字を配置していきます。元の位置都の差が小さくなるのはそのままの順序で並べた場合なので、ある文字を配置したいとき、残る文字をそのままの順序で並べてみて、条件に違反しないかどうかをチェックして、問題無ければその文字を配置します。条件に違反する場合は次の文字について同じことをする、という手順で順に決定できます。

コード

using VI = vector<int>;

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

#define PB( n ) push_back( n )

class EllysScrabble
{
public:
	string getMin( string letters, int maxDistance )
	{
		const int L = letters.size();

		vector<bool> used( L, false );

		string res;
		REP( iteration, 0, L )
		{
			bool done = false;

			for ( char c = 'A'; c <= 'Z'; c++ )
			{
				REP( i, 0, L )
				{
					if ( done )
					{
						break;
					}
					

					if ( !used[i] && letters[i] == c )
					{
						string tmp = res;
						tmp += letters[i];
						used[i] = true;

						REP( j, 0, L )
						{
							if ( !used[j] )
							{
								tmp += letters[j];
							}
						}
						if ( valid( letters, tmp, maxDistance ) )
						{
							res += letters[i];
							done = true;
						}
						else
						{
							used[i] = false;
						}
					}
				}
			}
		}

		return res;
	}

	bool valid( const string &S, const string &T, const int D )
	{
		for ( char c = 'A'; c <= 'Z'; c++ )
		{
			VI ps, qs;

			REP( i, 0, S.size() )
			{
				if ( S[i] == c )
				{
					ps.PB( i );
				}
				if ( T[i] == c )
				{
					qs.PB( i );
				}
			}

			REP( i, 0, ps.size() )
			{
				if ( D < abs( ps[i] - qs[i] ) )
				{
					return false;
				}
			}
		}

		return true;
	}
};