AtCoder Regular Contest #003 D : シャッフル席替え
問題概要
N(<=11)人の人が円周上に座っている。K(<20)回二人をランダムに選んで入れ替える。p[i]とq[i](i<20)が隣り合わないようになる確率を求める問題。
解法
許容誤差が小さいのでモンテカルロでよい。許容誤差の2乗*定数回程度回せば失敗確率は十分小さくなるらしい。
acceptされたコード
#include <cstdio> #include <algorithm> #include <sys/time.h> using namespace std; typedef double time_type; struct Timer{ time_type general_start_time; time_type get_time(){ struct timeval tv; gettimeofday(&tv, NULL); return (tv.tv_sec * 1000000LL + tv.tv_usec)/1e6 - general_start_time; } void set_start(){ struct timeval tv; gettimeofday(&tv, NULL); general_start_time = (tv.tv_sec * 1000000LL + tv.tv_usec)/1e6; } }; struct Xorshift{ unsigned int x, y, z, w, t; unsigned int rand(){ t = x ^ (x << 11); x = y; y = z; z = w; return w = ( (w ^ (w>>19)) ^ (t ^ (t>>8))); } Xorshift():x(123456789U), y(362436069U), z(521288629U), w(88675123U){} }; Timer timer; Xorshift rnd; const int MAX_N = 11; const int MAX_M = 20; int N, M, K; int ps[MAX_M][2]; int tmp[MAX_N + 1]; int inv[MAX_N]; void init(){ scanf("%d%d%d", &N, &M, &K); for(int i=0; i<M; ++i){ scanf("%d%d", ps[i]+0, ps[i]+1); } } bool check(){ for(int i=0; i<N; ++i){ tmp[i] = i; } for(int i=0; i<K; ++i){ int x = rnd.rand()%N; int y = rnd.rand()%N; for(;x==y;y=rnd.rand()%N); swap(tmp[x], tmp[y]); } for(int i=0; i<N; ++i){ inv[tmp[i]] = i; } for(int j=0; j<M; ++j){ int p = inv[ps[j][0]], q = inv[ps[j][1]]; int d = (p - q + N) % N; if(d == 1 || d == N - 1){ return false; } } return true; } double solve(){ int attempt = 0, accept = 0; for(;timer.get_time() < 9.5;){ ++attempt; if(check()){ ++accept; } } return (double)accept / attempt; } int main(){ timer.set_start(); init(); printf("%.5f\n", solve()); return 0; }