SRM337 D2H AnagramList - ry0u

TopCoder Statistics - Problem Statement
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

文字列が与えられる．並び替えで作られる文字列の中で，辞書順で$k$番目にあたる文字列を答える．左端から文字を決めていき，順番を合わせていく．同じ文字があるために，残りの文字列の順列を出すために，残りも文字数だけではなくmapで管理する．

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define REP(i,k,n) for(int i=k;i<(int)(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define mp make_pair

#define fi first
#define se second

using namespace std;
typedef long long ll;
typedef pair<int, int> P;

ll fact[25];

class AnagramList {
  public:
  string getAnagram(string s, int cnt) {
      memset(fact, 0, sizeof(fact));
      fact[0] = fact[1] = 1;
      REP(i, 2, 25) {
          fact[i] = i * fact[i-1];
      }

      map<char, int> m;
      rep(i, s.size()) {
          m[s[i]]++;
      }

      int sum = s.size();
      string ans = "";

      priority_queue<char, vector<char>, greater<char> > que;
      rep(i, s.size()) {
          que.push(s[i]);
      }

      while(m.size()) {
          bool flag = true;
          vector<char> v;
          each(it, m) v.push_back(it->fi);

          rep(i, v.size()) {
              m[v[i]]--;
              ll t = fact[sum - 1];
              each(it, m) {
                  t /= fact[it->se];
              }

              if(cnt < t) {
                  ans += v[i];
                  sum--;
                  flag = false;

                  if(m[v[i]] == 0) {
                      m.erase(v[i]);
                  }

                  break;
              } else {
                  cnt -= t;
                  m[v[i]]++;
              }
          }

          if(flag) return "";
      }

      return ans;
  }
};