SRM545 Div1 Easy(275), Div2 Medium(550) StrIIRec
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; }};