敗北。答えにかすりもしなかった。 乱択解を思いつけたことない気がする。

D - シャッフル席替え

制限時間が10秒かつ$N \le 11$の円順列は$3.6 {\rm e} 6$個なので、これに$K$と${}_NC_2$が掛かっても上手くやれば通るのだろうと思い、ずっとDPのようなものを考えていた。 前処理して区別する必要のない人々を同一視する等、色々試してみたが間に合わず。 答え見たらもっと単純だった。 許容誤差が変に大きいなとは感じたのだが、$({}_NC_2)^K \sim 6.4 {\rm e} 34$と大きいからかなあ、と勝手に納得し忘れてしまっていた。

解法

誤差は絶対誤差あるいは相対誤差の少なくとも片方が 2e−3 以下であれば許容する。

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

解答

   #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()は正確