ARC003 D - シャッフル席替え

ARC c++

arc003.contest.atcoder.jp

  • モンテカルロ法を使う問題。
  • 解法については以下のスライドを参照。技術的な内容だけではなくて表現がかなり面白かったです。こういうの好き。

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