naoya_t@topcoder

SRM402 Div1 Easy: RandomSort

過去問, 練習 | 18:04 |

DP的問題。メモ化しないとTLE。状態の数はn^nあるが、vector<double>だとメモリ64MB制限に引っかかる。map<int,double>で必要なものだけメモ化するのが吉。

#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)

template <typename T> T expt(T x, int n) // x^n
{
  T y=1; for(int i=0;i<n;i++) y*=x; return y;
}

class RandomSort {
  int n;
  vector<int> perm;
  //vector<double> memo;
  map<int,double> memo;

  int sig() {
    int s=0;
    tr(perm,it) s=s*n+(*it-1);
    return s;
  }
  double sw(){
    int key=sig();
    // if(memo[key]>=0) return memo[key];
    if(memo.find(key)!=memo.end()) return memo[key];

    set<pair<int,int> > s;
    rep(i,n){
      int p = perm[i];
      for(int j=i+1;j<n;j++){
        int q = perm[j];
        if (p>q) s.insert(make_pair(i,j));
      }
    }
    if (s.size() == 0) return memo[key] = 0;
    
    double cnt=0;
    tr(s,it){
      int i=it->first, j=it->second;
      int p=perm[i], q=perm[j];
      perm[i]=q; perm[j]=p;
      cnt += 1 + sw();
      perm[i]=p; perm[j]=q;
    }

    cnt /= s.size();
    return memo[key] = cnt;
  }
public:
  double getExpected(vector<int> permutation) {
    n=sz(permutation);
    perm = permutation;
    return sw();
  }
};