D - シャッフル席替え

解法

と許容誤差が大きいので乱択解。モンテカルロ法。

解答

   #include <random>
#include <ctime>
#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>
#include <cassert>
#define repeat_from(i,m,n) for (int i = (m); (i) < (n); ++(i))
#define repeat(i,n) repeat_from(i,0,n)
using namespace std;
bool ok(vector<int> const & a, set<pair<int,int> > const & forbidden) {
int n = a.size();
repeat (i,n) {
pair<int,int> p = { a[i], a[(i+1)%n] };
if (forbidden.count(p)) return false;
}
return true;
}
int main() {
clock_t start = clock();
int n, m, k; cin >> n >> m >> k;
set<pair<int,int> > forbidden;
repeat (i,m) {
int a, b; cin >> a >> b;
forbidden.emplace(a, b);
forbidden.emplace(b, a);
}
default_random_engine gen;
uniform_int_distribution<int> dist(0,n-1);
long long x = 0, y = 0;
while ((clock() - start) /(double) CLOCKS_PER_SEC < 9.5) {
vector<int> a(n);
repeat (i,n) a[i] = i;
repeat (i,k) {
int p = dist(gen);
int q = p; while (q == p) q = dist(gen);
swap(a[p], a[q]);
}
if (ok(a, forbidden)) ++ x;
++ y;
}
printf("%.12lf\n", x /(double) y);
return 0;
}


atcoderのclock()は正確