0w1

ARC 003 D - シャッフル席替え ( Monte Carlo, Hoeffdings Inequality )

Probability Monte Carlo Atcoder

D: シャッフル席替え - AtCoder Regular Contest 003 | AtCoder

www.slideshare.net
かなりわかりやすいスライドですが、覚えておきたいものをメモ：
Hoeffdings Inequality
● X1, X2, …, Xn を独立な Bernoulli 確率変数とする
● X = X1 + X2 + … + Xn とする
● このとき以下の式が成立する
● Pr( | X – E[X] | ≧ εn ) ≦ 2 e^( -2nε^2 )
● 確率論やべぇよ……やべぇよ……
● まあつまりなにが言いたいかというと
● 確率 p で表が出るコインを n 回投げたときに、表が出た回数が (p ± ε)n 回の範囲に収まらない 確率は 2 e^( -2nε^2 ) 以下になるという話です
● 許容誤差が 1/x 倍になっても保証AC率を変えな いためには、試行回数を x^2 倍にする必要がある

#include <bits/stdc++.h>
using namespace std;

signed main(){
  int N, M, K; cin >> N >> M >> K;
  vector< int > A( M ), B( M );
  vector< vector< int > > adj( N, vector< int >( N ) );
  for( int i = 0; i < M; ++i )
    cin >> A[ i ] >> B[ i ],
    adj[ A[ i ] ][ B[ i ] ] = adj[ B[ i ] ][ A[ i ] ] = 1;
  vector< int > seat( N );
  for( int i = 0; i < N; ++i )
    seat[ i ] = i;
  int okcnt = 0, ngcnt = 0;
  for( int t = 0; t < 1000000; ++t ){
    int ng = 0;
    vector< int > s = seat;
    for( int i = 0; i < K; ++i ){
      while( true ){
        int a = rand() % N;
        int b = rand() % N;
        if( a != b ){
          swap( s[ a ], s[ b ] );
          break;
        }
      }
    }
    for( int i = 0; i < N; ++i )
      if( adj[ s[ i ] ][ s[ ( i + 1 ) % N ] ] )
        ng = 1;
    okcnt += not ng;
    ngcnt += ng;
  }
  cout << fixed << setprecision( 6 ) << 1.0 * okcnt / ( okcnt + ngcnt ) << endl;
  return 0;
}