SRM 664 Div2 Hard BearSortDiv2

TopCoder Statistics - Problem Statement

• editorial を見て解いた。
• 問題見た時 DP とかかな？と思いきやそんなことはなかった。
• mergeSort なんでソート済みの部分列の段階で最終結果と前後が変わっていてはダメ。

class BearSortsDiv2 {
public:
    vector<int> whereIs;
    int count;
    bool less(int a, int b) {
            ++count;
            // 最終的な結果と一致するように 0.5 の確率で
            // 適切な比較ができていると考える
            return whereIs[a] < whereIs[b];
    }
    void mergeSort(int left, int right, vector<int> &T) {
        if (left+1>=right)
            return;

        int mid = (left+right)/2;

        mergeSort(left,mid,T);
        mergeSort(mid,right,T);
        // この段階で T[left...mid], T[mid...right] の順番は
        // 最終結果の seq の順と矛盾しない。
        // この後の sort は T[left...mid] ~ T[mid...right] 間のものだけ

        int p1 = left;
        int p2 = mid;
        vector<int> merged;

        while (p1 < mid || p2 < right)
        {
            if (p1 == mid)
            {
                merged.push_back(T[p2]);
                ++p2;
            }
            else if (p2 == right)
            {
                merged.push_back(T[p1]);
                ++p1;
            }
            else
            {
                if (less(T[p1], T[p2]))
                {
                    merged.push_back(T[p1]);
                    ++p1;
                }
                else
                {
                    merged.push_back(T[p2]);
                    ++p2;
                }
            }
        }
        for (int i = left; i < right; ++i)
            T[i] = merged[i-left];
}
double getProbability(vector <int> seq) {
        int N = seq.size();
        whereIs.resize(N+1);
        count = 0;

        //
        // mergeSort の特徴として mregeSort 済みの部分列の再ソートはないので
        // 最終的な結果 seq になるには各 less の段階で適切な比較ができてなければならない。
        //
        // よって適切な比較ができたときの merge ソートの比較回数 k にたいして
        // 0.5^k が最終的なソート結果となる確率
        //
        vector<int> T(N);
        REP(i,N)
        {
            T[i] = i+1;
            whereIs[seq[i]] = i; // 適切な比較をするための逆参照用
        }
        mergeSort(0,N,T);
        // 0.5^k
        return log(0.5)*count;
}
};