山傘のプログラミング勉強日記

プログラミングに関する日記とどうでもよい雑記からなるブログです。

[AtCoder] C - Ordinary Beauty

問題

SoundHound Inc. Programming Contest 2018 -Masters Tournament- のC問題です。

C - Ordinary Beauty

f:id:yamakasa3:20180708152952p:plain

確率と期待値の問題です。おそらく、モンテカルロ法で解けないことから、プログラミングとはあまり関係ないですね。

解説を見ても良く分からなかったので、ネットの海に溺れることに・・・。

考え方

和の期待値=期待値の和というのは期待値の線形性というキーワードとしてよく出てきます。

この問題を考える上で、似たような問題を考えます。問題の次元を落としても見えてこなかったので。

 n回コインを投げて表が出る期待値は?

コインを n 回投げて表が出る期待値 Eを考えます。

コインは表か裏かしかないので、それぞれ出る確率を \dfrac{1}{2}とします。

 1回なげるとき

 E = 0 \times \dfrac{1}{2} + 1 \times \dfrac{1}{2}

 = \dfrac{1}{2}

 2回なげるとき

 E = 0 \times \dfrac{1}{4} + 1 \times \dfrac{2}{4} + 2 \times \dfrac{1}{4}

 = 1

 n 回投げるとき

 E = 0 \times \dfrac{1}{2^n} + 1 \times \dfrac{ {}_n \mathrm{C} _1}{2^n} + 2 \times \dfrac{ {}_n \mathrm{C} _2}{2^n} + \cdots + n \times \dfrac{1}{2^n}

となるんですが、このような計算を行わなくても期待値の線形性を使えば答えは出せます。

期待値の線形性を元に考える

 k 回目にコインを投げて表が出る確率は \dfrac{1}{2} なので、 n 回投げてコインの表が出る期待値は、

 E = \dfrac{n}{2}

となります。

コインの表を 0、裏を 1 とし、 k回目にコインの出る値を確率変数 X_k  (X_k = 0, 1) とします。また、

 E[X_k] = \dfrac{1}{2}

となります。ここで、求めたい値は、

 E = E[X_1 + X_2 + \cdots + X_n]

であり、期待値の線形性から、

 E[X_1 + X_2 + \cdots + X_n]  = E[X_1] + E[X_2] + \cdots + E[X_n]

 = nE[X_1] = \dfrac{n}{2}

感覚的には、コインを n 回投げたら半分は表が出るやろという感じですね。

この問題の考え方

期待値の線形性について調べていると、この問題と似たようなものがありました。

mathtrain.jp

上記のサイトの「期待値の線形性の応用例2」と似ています。

 d = 0 のとき

 d = 0 のとき、別の言葉で言い換えると、 1 ~ nの値が出るサイコロを m 回投げて、同じ目が連続して出る期待値を求める問題となります。

サイコロを二回投げて初めて連続する可能性があるので、最大で m - 1 回連続して同じ目が出る可能性があります。なので、数字を並べたとき、候補は m - 1 箇所となります。

同じ目の組み合わせは、 (1, 1), (2, 2), \cdots (n, n) n 通りあります。二回サイコロを投げたときの場合の数は n^2 となり、1回連続して同じ目が出る確率は、

 \dfrac{n}{n^2}

となります。したがって求める期待値 E

 E = \dfrac{m - 1}{n}

となります。

 d \neq 0 のとき

組み合わせは、

 (1, 1 + d), (2, 2 + d), \cdots ,(n - d, n)

 (d + 1, d), (d + 2, 2), \cdots ,(n, n - d)

 2(n - d)通りあるので、求める期待値は

 \dfrac{2(m-1)(n - d)}{n^2}

感想

いまいちしっくりきません。他の解説を待ちましょう。

確率変数のところで、1回目の表が出る確率は、

 P(X_1 = 0) = \dfrac{1}{2}

と表します。久しぶりに確率変数とか使ったので表記が正しいかは保証しません。