SRM545 Div1 Easy

275

先頭から1文字ずつ作る。

ある文字を次に付け足す場合、
(これまでに作った文字列) + (次に付け足す文字) + (残りを降順に並べた文字列)
で出来る文字列がこれ以降で inv の数を最大にでできて、辞書順で最も大きい。

あとは、minInv と minStr の条件を満たせる範囲で最も辞書順で小さい文字を順に付け加えていくだけでいい。




本番で提出したコードからコメント等を消したヤツ。

int f(string s)
{
  int cnt = 0;
  for (int i = 0; i < (int)s.size(); ++i) {
    for (int j = i + 1; j < (int)s.size(); ++j) {
      cnt += (s[i] > s[j]);
    }
  }
  return cnt;
}

class StrIIRec {
public:
  string recovstr(int n, int inv, string minStr)
  {
    string s;
    vector<char> v;
    for (int i = 0; i < (int)n; ++i) {
      v.push_back('a' + i);
    }

    for (int loop = n; loop--; ) {
      const int size = v.size();
      int mx[size];
      string mxS[size];

      for (int i = 0; i < (int)v.size(); ++i) {
        string t, u;
        for (int j = 0; j < (int)v.size(); ++j) {
          if (i != j) t += v[j];
        }
        reverse(t.begin(), t.end());
        u = s + v[i] + t;
        mx[i] = f(u);
        mxS[i] = u;
      }

      for (int i = 0; i < (int)v.size(); ++i) {
        if (mxS[i] < minStr) continue;
        if (inv <= mx[i]) {
          s += v[i];
          v.erase(v.begin() + i);
          break;
        }
      }
    }

    if (v.size()) return "";
    if ((int)s.size() != n) return "";
    return s;
  }
};