SRM402

この時期のSRMは問題分が短いのが多い気がする。読みやすいのはいいけど、内容を理解するのに時間がかかってしまう…。
こんかいは２問めが450だったので解けるかと思ったけど、無理だった。div1midはやる気が出ないので、これから250だけを解くことに決めた。

146/250

• 再帰で数える
• 8,7,6,5,4,3,2,1を入力してみると時間オーバー…
• メモ化してみよう
• 答えが合わない…
• メモ化の方法が間違ってたみたい
• Accept

map<int,double> memo;
class RandomSort {
public:
  int toint(vector<int> perm){
    int ret = 0;
    REP(i,perm.size()){
      ret += perm[i] * pow(9.0,(double)i);
    }
    return ret;
  }
  double calc(vector<int> &perm,int c){
    double count = 0;
    FOR(i,0,perm.size()){
      FOR(j,i+1,perm.size()){
        if(perm[i]>perm[j]) count+=1;
      }
    }
    if(count==0) return c;
    int p_n = toint(perm);
    if(memo.find(p_n)!=memo.end()) return memo[p_n]+c;
    double ret = 0;
    REP(i,perm.size()){
      FOR(j,i+1,perm.size()){
        if(perm[i]>perm[j]){
          swap(perm[i],perm[j]);
          ret += calc(perm,c+1)/count;
          swap(perm[i],perm[j]);
        }
      }
    }
    memo[p_n] = ret-c;
    return (ret);
  }
  double getExpected(vector <int> permutation) {
    double result = calc(permutation,0);
    return result;
  }

  

};