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); } };