現代の ABC-E にも出そうな DP
問題概要

$1, 2, \dots, N$ の順列 $p_{1}, p_{2}, \dots, p_{N}$ が与えられる。この順列に対して、以下の操作を繰り返していく
$i \lt j$ かつ $p_{i} \gt p_{j}$ であるような $(i, j)$ を一様ランダムに選び、
$p_{i}$ と $p_{j}$ を swap する
ソートされた状態になるまでの回数の期待値を求めよ。
制約

$1 \le N \le 8$
考えたこと

期待値と言われると、期待値の線形性が思い浮かぶが...... $N$ が小さいので DP してしまおう。
dp[p] ← 順列 $p$ をソートするのに要する回数の期待値
計算量は $O(N! N^{2})$ となる。
コード

#include <bits/stdc++.h>
using namespace std;
using pint = pair<int, int>;
using pll = pair<long long, long long>;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

#define REP(i, n) for (long long i = 0; i < (long long)(n); ++i)
#define REP2(i, a, b) for (long long i = a; i < (long long)(b); ++i)
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, deque<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, set<T> P)
{ for(auto it : P) { s << "<" << it << "> "; } return s; }
template<class T> ostream& operator << (ostream &s, multiset<T> P)
{ for(auto it : P) { s << "<" << it << "> "; } return s; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ for(auto it : P) { s << "<" << it.first << "->" << it.second << "> "; } return s; }


map<vector<int>, double> dp;
double dfs(vector<int> &v) {
    if (dp.count(v)) return dp[v];
    
    vector<pint> revs;
    for (int i = 0; i < v.size(); ++i) {
        for (int j = i+1; j < v.size(); ++j) {
            if (v[i] > v[j]) revs.emplace_back(i, j);
        }
    }
    if (revs.empty()) return dp[v] = 0.0;
    
    double res = 0;
    for (auto [p, q] : revs) {
        swap(v[p], v[q]);
        res += dfs(v);
        swap(v[p], v[q]);
    }
    return dp[v] = res / revs.size() + 1.0;
}

class RandomSort {
public:
    double getExpected(vector <int> permutation) {
        return dfs(permutation);
    }
};



// BEGIN CUT HERE
namespace moj_harness {
    int run_test_case(int);
    void run_test(int casenum = -1, bool quiet = false) {
        if (casenum != -1) {
            if (run_test_case(casenum) == -1 && !quiet) {
                cerr << "Illegal input! Test case " << casenum << " does not exist." << endl;
            }
            return;
        }
        
        int correct = 0, total = 0;
        for (int i=0;; ++i) {
            int x = run_test_case(i);
            if (x == -1) {
                if (i >= 100) break;
                continue;
            }
            correct += x;
            ++total;
        }
        
        if (total == 0) {
            cerr << "No test cases run." << endl;
        } else if (correct < total) {
            cerr << "Some cases FAILED (passed " << correct << " of " << total << ")." << endl;
        } else {
            cerr << "All " << total << " tests passed!" << endl;
        }
    }
    
    static const double MAX_DOUBLE_ERROR = 1e-9; static bool topcoder_fequ(double expected, double result) { if (isnan(expected)) { return isnan(result); } else if (isinf(expected)) { if (expected > 0) { return result > 0 && isinf(result); } else { return result < 0 && isinf(result); } } else if (isnan(result) || isinf(result)) { return false; } else if (fabs(result - expected) < MAX_DOUBLE_ERROR) { return true; } else { double mmin = min(expected * (1.0 - MAX_DOUBLE_ERROR), expected * (1.0 + MAX_DOUBLE_ERROR)); double mmax = max(expected * (1.0 - MAX_DOUBLE_ERROR), expected * (1.0 + MAX_DOUBLE_ERROR)); return result > mmin && result < mmax; } }
    double moj_relative_error(double expected, double result) { if (isnan(expected) || isinf(expected) || isnan(result) || isinf(result) || expected == 0) return 0; return fabs(result-expected) / fabs(expected); }
    
    int verify_case(int casenum, const double &expected, const double &received, clock_t elapsed) { 
        cerr << "Example " << casenum << "... "; 
        
        string verdict;
        vector<string> info;
        char buf[100];
        
        if (elapsed > CLOCKS_PER_SEC / 200) {
            sprintf(buf, "time %.2fs", elapsed * (1.0/CLOCKS_PER_SEC));
            info.push_back(buf);
        }
        
        if (topcoder_fequ(expected, received)) {
            verdict = "PASSED";
            double rerr = moj_relative_error(expected, received); 
            if (rerr > 0) {
                sprintf(buf, "relative error %.3e", rerr);
                info.push_back(buf);
            }
        } else {
            verdict = "FAILED";
        }
        
        cerr << verdict;
        if (!info.empty()) {
            cerr << " (";
            for (int i=0; i<(int)info.size(); ++i) {
                if (i > 0) cerr << ", ";
                cerr << info[i];
            }
            cerr << ")";
        }
        cerr << endl;
        
        if (verdict == "FAILED") {
            cerr << "    Expected: " << expected << endl; 
            cerr << "    Received: " << received << endl; 
        }
        
        return verdict == "PASSED";
    }

    int run_test_case(int casenum__) {
        switch (casenum__) {
        case 0: {
            int permutation[]         = {1,3,2};
            double expected__         = 1.0;

            clock_t start__           = clock();
            double received__         = RandomSort().getExpected(vector <int>(permutation, permutation + (sizeof permutation / sizeof permutation[0])));
            return verify_case(casenum__, expected__, received__, clock()-start__);
        }
        case 1: {
            int permutation[]         = {4,3,2,1};
            double expected__         = 4.066666666666666;

            clock_t start__           = clock();
            double received__         = RandomSort().getExpected(vector <int>(permutation, permutation + (sizeof permutation / sizeof permutation[0])));
            return verify_case(casenum__, expected__, received__, clock()-start__);
        }
        case 2: {
            int permutation[]         = {1};
            double expected__         = 0.0;

            clock_t start__           = clock();
            double received__         = RandomSort().getExpected(vector <int>(permutation, permutation + (sizeof permutation / sizeof permutation[0])));
            return verify_case(casenum__, expected__, received__, clock()-start__);
        }
        case 3: {
            int permutation[]         = {2,5,1,6,3,4};
            double expected__         = 5.666666666666666;

            clock_t start__           = clock();
            double received__         = RandomSort().getExpected(vector <int>(permutation, permutation + (sizeof permutation / sizeof permutation[0])));
            return verify_case(casenum__, expected__, received__, clock()-start__);
        }

        // custom cases

/*      case 4: {
           int permutation[]         = ;
           double expected__         = ;

           clock_t start__           = clock();
           double received__         = RandomSort().getExpected(vector <int>(permutation, permutation + (sizeof permutation / sizeof permutation[0])));
           return verify_case(casenum__, expected__, received__, clock()-start__);
       }*/
/*      case 5: {
           int permutation[]         = ;
           double expected__         = ;

           clock_t start__           = clock();
           double received__         = RandomSort().getExpected(vector <int>(permutation, permutation + (sizeof permutation / sizeof permutation[0])));
           return verify_case(casenum__, expected__, received__, clock()-start__);
       }*/
/*      case 6: {
           int permutation[]         = ;
           double expected__         = ;

           clock_t start__           = clock();
           double received__         = RandomSort().getExpected(vector <int>(permutation, permutation + (sizeof permutation / sizeof permutation[0])));
           return verify_case(casenum__, expected__, received__, clock()-start__);
       }*/
        default:
            return -1;
        }
    }
}
 

int main(int argc, char *argv[]) {
    if (argc == 1) {
        moj_harness::run_test();
    } else {
        for (int i=1; i<argc; ++i)
            moj_harness::run_test(atoi(argv[i]));
    }
}
// END CUT HERE
けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

TopCoder SRM 402 DIV1 Easy - RandomSort (本番 334 人)

問題概要

制約

考えたこと

コード
