現代の ABC-E にも出そうな DP
問題概要
の順列 
が与えられる。この順列に対して、以下の操作を繰り返していく
かつ 
であるような 
を一様ランダムに選び、
と 
を swap する
ソートされた状態になるまでの回数の期待値を求めよ。
制約
考えたこと
期待値と言われると、期待値の線形性が思い浮かぶが......
が小さいので DP してしまおう。
dp[p] ← 順列 
をソートするのに要する回数の期待値
計算量は 
となる。
コード
#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);
}
};
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__);
}
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]));
}
}
= "I"
= "O"
= "I"
が交差が奇数の等差数列でなければならない
は偶数
の中点は "O" となる
を固定
を固定
の
番目と
番目の間に "I" がない
番目より右側に "I" がない
