ABC008-C：Coin

数学

問題

https://beta.atcoder.jp/contests/abc008/tasks/abc008_3

N 枚のコインがある。それぞれ正の整数が書いてある。このコインを無作為にすべての組み合わせが同じ確率で出てくるように一列に並べる。以下の操作をした時の表を向いているコインの数の期待値を求めよ。

操作

  1. すべてのコインを表向きにする
  2. 左端から順番に、現在見ているコインの右側にあるコインのうち、現在見ているコインに書かれている整数の倍数になっているコインについて裏表をひっくり返す。

制約

  • 1 <= n <= 100
  • 1 <= c_i <= 109
    入力値は整数

考え方

問題文に書かれている操作をナイーブにシミュレーションすると計算量が O(N!) となり間に合わない。期待値の性質を用いて、問題文の読み替えをする。

求める期待値は、・・・

⇔すべての組み合わせのうち、表を向いているコインの枚数の総合計を N! で割った値
⇔各コインについて何通りの並べ方で表を向くのかという方針で計算
　表を向いているコインの枚数の総合計は組み合わせごとに数えても、各コインが全組み合わせのうち、何通りの組み合わせで表を向くのかという数え方で数えても一致するため。

  • 全体の総和を求めた後、 N! で割った結果 = それぞれの要素を N! で割った値の合計
  • それぞれのコインごとに表を向いている組み合わせを N! で割った値 = そのコインが表を向いている確率

である。対象のコインが表を向いた状態で終了する確率を求めることに気づければ後は容易。
表を向いた状態で終了するということは、あるコイン C_i について c_n に含まれる C_i の約数の数を d_i とすると、求める確率 p_i は

(i) d_i が奇数のとき
p_i = 1/2

(ii) d_i が奇数のとき
p_i = ((d_i)/2 + 1) / (d_i + 1) ⇔ (d_i + 2) / ( 2 * d_i + 2)

である。よって求める期待値は Σ [i = 0 ->i = n-1] p_i で求められる。

       public void solve(int testNumber, InputReader in, PrintWriter out) {

            int n = in.nextInt();
            long[] c = in.nextLongArray(n);

            double[] d = new double[n];
            for (int i = 0; i < n; i++) {
                double count = 0;
                for (int j = 0; j < n; j++) {
                    if (i == j) continue;
                    if (c[i] % c[j] == 0) {
                        count++;
                    }
                }
                d[i] = count;
            }

            double ans = 0.0;
            for (int i = 0; i < n; i++) {
                if (d[i] % 2 == 0) {
                    ans += (d[i] + 2)/(2*d[i] + 2);
                } else {
                    ans += 0.5;
                }
            }

            out.println(ans);

        }

ポイント

  • 求める条件の全組み合わせ / 事象の全組み合わせ = 求める条件が発生する確率