SRM 664 div2 hard:BearSortsDiv2
なんかやけに簡単な気がする。
解法
答えは (LESS 関数を使った数) * log(0.5) となる。
そのため, merge 関数を実際に動かしてみて LESS を使う回数をシミュレートしていけば良い。
const double LOG = log(0.5); const int MAXN = 44; int mul = 0; vector<int> seq; int ind[MAXN]; bool cmp(int a, int b) { return ind[a] < ind[b]; } void dfs(int l, int r) { if (l+1 >= r) return; int mid = (l+r)/2; dfs(l, mid); dfs(mid, r); vector<int> L, R; for (int i = l; i < mid; i++) L.push_back(i+1); for (int i = mid; i < r; i++) R.push_back(i+1); sort(L.begin(), L.end(), cmp); sort(R.begin(), R.end(), cmp); int p1 = l, p2 = mid; while (p1 < mid || p2 < r) { if (p1 == mid) p2++; else if (p2 == r) p1++; else { if (cmp(L[p1-l], R[p2-mid])) p1++; else p2++; mul++; } } } class BearSortsDiv2 { public: double getProbability(vector <int> seq) { mul = 0; int N = seq.size(); ::seq = seq; for (int i = 0; i < N; i++) ind[seq[i]] = i; dfs(0, N); return LOG*mul; } };