[AtCoder] C - Ordinary Beauty
問題
SoundHound Inc. Programming Contest 2018 -Masters Tournament- のC問題です。
確率と期待値の問題です。おそらく、モンテカルロ法で解けないことから、プログラミングとはあまり関係ないですね。
解説を見ても良く分からなかったので、ネットの海に溺れることに・・・。
考え方
和の期待値=期待値の和というのは期待値の線形性というキーワードとしてよく出てきます。
この問題を考える上で、似たような問題を考えます。問題の次元を落としても見えてこなかったので。
回コインを投げて表が出る期待値は?
コインを 回投げて表が出る期待値を考えます。
コインは表か裏かしかないので、それぞれ出る確率をとします。
回なげるとき
回なげるとき
回投げるとき
となるんですが、このような計算を行わなくても期待値の線形性を使えば答えは出せます。
期待値の線形性を元に考える
回目にコインを投げて表が出る確率は なので、 回投げてコインの表が出る期待値は、
となります。
コインの表を、裏を とし、回目にコインの出る値を確率変数 とします。また、
となります。ここで、求めたい値は、
]
であり、期待値の線形性から、
]
感覚的には、コインを 回投げたら半分は表が出るやろという感じですね。
この問題の考え方
期待値の線形性について調べていると、この問題と似たようなものがありました。
上記のサイトの「期待値の線形性の応用例2」と似ています。
のとき
のとき、別の言葉で言い換えると、の値が出るサイコロを 回投げて、同じ目が連続して出る期待値を求める問題となります。
サイコロを二回投げて初めて連続する可能性があるので、最大で 回連続して同じ目が出る可能性があります。なので、数字を並べたとき、候補は 箇所となります。
同じ目の組み合わせは、 の 通りあります。二回サイコロを投げたときの場合の数は となり、1回連続して同じ目が出る確率は、
となります。したがって求める期待値 は
となります。
のとき
組み合わせは、
と
の通りあるので、求める期待値は
感想
いまいちしっくりきません。他の解説を待ちましょう。
確率変数のところで、1回目の表が出る確率は、
と表します。久しぶりに確率変数とか使ったので表記が正しいかは保証しません。