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;
}