SRM545 Div1 Easy(275), Div2 Medium(550) StrIIRec

StrIIRe

i文字目までを決めて反転数が最大になるのは、残りの文字が降順の場合。辞書順でminStr以降という条件を満たすように先頭から文字を決めていく。…dcbaは辞書順最後で反転数がn(n-1)/2なので、答えは常に存在する。

#include <string>
#include <vector>
using namespace std;

int inv(string str)
{
    int c = 0;
    int n = (int)str.size();
    for ( int i=0; i<n; i++ )
    for ( int j=i+1; j<n; j++ )
        if ( str[i]>str[j] )
            c++;
    return c;
}

class StrIIRec{public:
string recovstr( int n, int minInv, string minStr )
{
    for ( int i=(int)minStr.size(); i<n; i++ )
        minStr += "a";
    
    string ans;

    vector<bool> U('a'+n);

    for ( int i=0; i<n; i++ )
    {
        char c = ans>minStr.substr(0,i) ? 'a' : minStr[i];
        for ( ; c<'a'+n; c++ )
        if ( !U[c] )
        {
            string s = ans + c;
            vector<bool> u = U;
            u[c] = true;

            for ( int j=i+1; j<n; j++ )
            {
                for ( char t='a'+n-1; t>='a'; t-- )
                if ( !u[t] )
                {
                    s += string(1,t);
                    u[t] = true;
                    break;
                }
            }

            if ( inv(s)>=minInv )
            {
                ans += c;
                U[c] = true;
                break;
            }
        }
    }

    return ans;
}};