TopCoder SRM 563, Division 1, Level 1 : FoxAndHandle

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12331&rd=15185

概要

二つの文字列 X, Y を先頭からマージしたものを Z とする。
既にマージされた文字列 S が与えられる。
X は S の部分列、Y は X を並び替えたものであるとする。
X としてありうる文字列の内、辞書順最小となるものを答えよ。

解法

先頭から順に、できるだけ早い文字を埋めていきます。
文字の追加は、その都度、残りの文字の内で早い文字から順に追加できるかどうか試していきます。
追加できる条件は、「その文字より後ろで、残りの文字の出現回数が足りているかどうか」です。

コード

#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 )
#define EXIST( c, e ) ( (c).find( e ) != (c).end() )

class FoxAndHandle
{
public:
	string lexSmallestName(string S)
	{
		const int N = S.size();

		string res;

		vector<char> chars( getChars( S ) ); // 使う文字
		set<int> done;

		int last = -1;

		REP( i, 0, N / 2 )
		{
			REP( j, 0, chars.size() )
			{
				if ( EXIST( done, j ) ) // 既に入れた文字
				{
					continue;
				}

				int pos = S.find( chars[j], last + 1 );

				if ( ok( S, chars, j, pos, done ) ) // この文字を入れても条件を満たす
				{
					res += chars[j];
					done.insert( j );
					last = pos;
					break;
				}
			}
		}

		return res;
	}

	vector<char> getChars( string s )
	{
		sort( ALL( s ) );

		vector<char>res;

		for ( int i = 0; i < s.size(); i += 2 )
		{
			res.PB( s[i] );
		}

		return res;
	}

	bool ok( string s, vector<char> chars, int idx, int pos, set<int> done )
	{
		set<int> vanished;

		REP( i, 0, chars.size() )
		{
			if ( i == idx || EXIST( done, i ) )
			{
				continue;
			}

			bool ok = false;

			REP( j, pos, s.size() )
			{
				if ( EXIST( vanished, j ) ) // 既に数えた位置
				{
					continue;
				}

				if ( s[j] == chars[i] ) // s[j] := 探している文字
				{
					vanished.insert( j );
					ok = true;
					break;
				}
			}

			if ( !ok )
			{
				return false;
			}
		}

		return true;
	}
};