TopCoder SRM 664 Div2 Hard : BearSorts

問題

---

TopCoder Statistics - Problem Statement
大小比較の際に、真偽が50%の確率でランダムに返ってくる恐ろしいマージソートがある。
入力として、このマージソートでソート済みの配列seqが与えられる。
[1,2..N]の配列をこのマージソートにかけたときに、seqになる確率の自然対数をとった値を求める。

制約

---

要素数N: 1<=N<=40

解法

---

真偽の確率が等しいから比較回数をカウントして0.5をその数だけかければ良い。あとはlogをとって返す。
seqから普通のマージソートを行うとカウント数が異なるので注意。

int[] T,sorted;
int n,cnt = 0;

public double getProbability(int[] seq) {
    n = seq.length;
    sorted = seq.clone();
    T = new int[n];
    for (int i=0; i<n; i++) {
        T[i] = i+1;
    }
    merge(0,n);
    return Math.log(Math.pow(0.5,cnt));
}

void merge(int l, int r) {
    if (l+1 >= r) return;
    int m = (l+r)/2;
    merge(l,m);
    merge(m,r);
    ArrayList<Integer> list = new ArrayList<Integer>();
    int p1 = l;
    int p2 = m;
    while (p1 < m || p2 < r) {
        if (p1 == m) {
            list.add(T[p2]);
            p2++;
        }else if (p2 == r) {
            list.add(T[p1]);
            p1++;
        }else {
            cnt++;
            if (less(T[p1],T[p2])) {
                list.add(T[p1]);
                p1++;
            }else {
                list.add(T[p2]);
                p2++;
            }
        }
    }

    for (int i=l; i<r; i++) {
        T[i] = list.get(i-l);
    }
}

boolean less(int a, int b) {
    for (int i=0; i<n; i++) {
        if (sorted[i] == a) {
            return true;
        }else if (sorted[i] == b){
            return false;
        }
    }
    return false;
}