TopCoder SRM 545, Div1-L1/Div2-L2 : StrIIRec

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12025&rd=14737

概要

文字列 S の"転倒数"を次のように定める。

• i < j なる i, j について、S[i] > S[j] を満たす i, j の組の数

アルファベットの先頭 n 文字を組み合わせた文字列を考える。
次の二つの条件を満たす辞書順最小の文字列を求めよ。
（存在しない場合は空文字列を返せ）

• 転倒数が minInv 以上
• 辞書順で minStr 以上

解法

先頭から順に、できるだけ早い文字を埋めていきます。
ある文字を入れられる条件は、「文字を入れても辞書順で minInv 以上で、続く文字を最適に選ぶことで転倒数を minInv 以上にできる」です。
転倒数は、文字を降順に並べると最大になるので、続く文字を降順に並べた場合の転倒数を考えればよいです。

コード

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

class StrIIRec
{
public:
	string recovstr( int n, int minInv, string minStr )
	{
		vector<bool> used( n, false );

		string res;

		REP( i, 0, n )
		{
			REP( j, 0, n )
			{
				if ( used[j] || // 既に使った文字
					 res + (char)( 'a' + j ) < minStr.substr( 0, res.size() + 1 ) ||
					 calcInv( res + (char)( 'a' + j ), j, used ) < minInv )
				{
					continue;
				}

				res += 'a' + j;
				used[j] = true;
				break;
			}
		}

		return res.size() == n ? res : "";
	}

	int calcInv( string str, int cur, vector<bool> used )
	{
		// わかりやすさのため、実際に最適に埋める
		for ( int i = used.size() - 1; 0 <= i; i-- )
		{
			if ( used[i] || i == cur )
			{
				continue;
			}

			str += 'a' + i;
		}

		int res = 0;

		REP( i, 0, str.size() )
		{
			REP( j, i + 1, str.size() )
			{
				res += str[i] > str[j];
			}
		}

		return res;
	}
};