SRM405 Div2 Hard

1000

まさかのバックトラック

string rec(priority_queue<int> q, char next, string s, int L)
{
  if (L < s.size() + q.size()) return ""; 
  if (L == s.size() + q.size()) {
    while (q.size()) {
      s += (char)(-1 * q.top());
      q.pop();
    }
    return s;
  }

  priority_queue<int> p;
 
  if (q.size()) {
    p = q;
    string t = s + (char)(-1 * p.top());   
    p.pop();
    t = rec(p, next, t, L);
    if (t.size()) return t;
  }

  for (int i = s.size(); i < L; ++i) {
    if (s.size() + q.size() + s.size() + 1 <= L) {
      p = q;
      for (int j = 0; j < (int)s.size(); ++j) {
        p.push(-1 * next);
      }
      string t = rec(p, next + 1, s + next, L);
      if (t.size()) return t;
    }
  }
  return "";
}

class IdealString {
public:
  string construct(int L)
  {
    return rec(priority_queue<int>(), 'A', "", L);
  }
};