SRM402 Div2 Hand

1000

数字は多くても 8 個しかないので、とりあえずメモしながら全部試す。
+1.0 する必要があることに全然気がつかなかった。

const int N = 8;
int ns[N];
map<string, double> memo;

string f(int size)
{
  string s;
  for (int i = 0; i < (int)size; ++i) {
    s += ns[i] + 'A';
  }
  return s;
}

double rec(int size)
{
  string s = f(size);
  if (memo.count(s)) return memo[s];
  double ret = 0;
  int cnt = 0;
  for (int i = 0; i < (int)size; ++i) {
    for (int j = i + 1; j < (int)size; ++j) {
      if (ns[i] > ns[j]) {
        swap(ns[i], ns[j]);
        ret += rec(size);
        ++cnt;
        swap(ns[i], ns[j]);
      }
    }
  }
  if (cnt == 0) return memo[s] = 0;
  return memo[s] = ret / cnt + 1.0;
}

class RandomSort {
public:
  double getExpected(vector <int> P)
  {
    copy(P.begin(), P.end(), ns);
    return rec(P.size());
  }
};