読者です 読者をやめる 読者になる 読者になる

SRM402 Div1Easy RandomSort

解法
メモ化再帰

class RandomSort {
public:
  map<vector<int>, double> mp;
  double getExpected(vector <int> permutation) {
    if(mp.count(permutation)) {
      return mp[permutation];
    }
    
    double ret = 0.;
    double cnt = 0.;
    for(int i=0; i<permutation.size(); i++) {
      for(int j=i+1; j<permutation.size(); j++) {
        if(permutation[i] > permutation[j]) {
          swap(permutation[i], permutation[j]);
          ret += getExpected(permutation) + 1;
          cnt ++;
          swap(permutation[i], permutation[j]);
        }
      }
    }
    
    return mp[permutation] = (cnt == 0 ? 0 : ret / cnt);
  }
};