mayoko’s diary

プロコンとかいろいろ。

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