ARC003 D - シャッフル席替え
- モンテカルロ法を使う問題。
- 解法については以下のスライドを参照。技術的な内容だけではなくて表現がかなり面白かったです。こういうの好き。
ARC#003D from nullmineral
www.slideshare.net
- Hoeffding 不等式については以下が参考になる。
Hoeffdingの不等式 - 機械学習の「朱鷺の杜Wiki」
http://www.math.cm.is.nagoya-u.ac.jp/~kanamori/lecture/lec.2008.1st.stat-ana/01.pdf
- 何回シミュレーションすればいいのかについてなんだけど、他の人のコードを見ると施行回数が十分なだけループするのではなくて、制限時間分ループするという手もあるみたい。
class D_ShuffleDesk { public: void solve(void) { // 単純な数え上げだと O((N*N)^K) になって計算不可 // 許容誤差が大きいのでモンテカルロ法で解く // // 確率 p で 1, 1-p で 0 をとる確率分布を Bernoulli 分布という // // X を Bernoulli 分布に従う確率変数とすると // // P(X=1) = p // P(X=0) = 1-p // // である。 // // --- Hoeffding 不等式(Bernoulli 確率変数版) --- // // X1,...,Xn が独立な Bernoulli 確率変数とするとき // n // P(|1/n * Σ Xi - p| ≧ ε) ≦ 2 * e^(-2*n*ε^2) // i=1 // となる。 // int N,M,K; cin>>N>>M>>K; vector<vector<bool>> bad_pair(N,vector<bool>(N,false)); REP(i,M) { int a,b; cin>>a>>b; bad_pair[a][b] = bad_pair[b][a] = true; } // // テストケースが 100 個あるとすると // 0.9999^100 = 0.9900... より // 1ケース正当する確率が 99.99% くらいならよい // ε=0.002 として Hoeffding 不等式より // // 2*e^(-2*n*ε^2) < (1.0-0.9999) = (誤答確率) // <=> n > 1.23794e+06 // // 1300000 くらい施行すれば十分 // double p = 0.0; const int n = 1300000; vector<int> idx(N); // O(n*(K+N)) REP(i,n) { // そのままシュミレーション iota(RANGE(idx),0); auto tmp(idx); REP(k,K) { random_shuffle(RANGE(tmp)); swap(idx[tmp[0]],idx[tmp[1]]); } int X = 1; REP(j,N) { if ( bad_pair[idx[j]][idx[(j+1)%N]] ) X = 0; } p += X; } p /= n; cout<<setprecision(20)<<p<<endl; } };