こんにちは!
競技プログラミング中毒者のhotmanです
競技プログラミングの事しかわからなくなってしまったので、競技プログラミングの事を書きます
数学に強くなりたいのと、ゴリゴリ競プロだとmis.wの誰も読んでくれなくなる気がしたので数学要素強めでいきます
この知識を使う競プロの問題はあまり見ないので、思考パズルのつもりで読んで頂けるとありがたいです
後、解説記事しか書けないので解説記事を書きます
関連記事(おすすめの記事)
maspyさんによる記事(これがきっかけで競プロ界に形式的冪級数が流行りました)
maspypy.com
これはmis.wの幽霊サークル員である所のSenが書いた記事で、僕も関わっている記事です
sen-comp.hatenablog.com
sen-comp.hatenablog.com
これ、難しいのも乗ってます
http://www.aoni.waseda.jp/sadayosi/course/past/comb15/chapter1.pdf
一通り読み終わったらこれを解いて見てもいいかもしれません
基礎の確認によい問題です
atcoder.jp
解説
コインをN回投げます。表がK回でる場合の数を求めなさい
中学受験ですね。
N個の物からK個選ぶ場合の数と同じなので通り
これを形式的べき級数を用いて考えると
となります。
ここで、1は裏、xは表に対応しています
でもってxをK回選ぶとの項になる、二項定理の基本的な考え方です
サイコロをN回投げます。出た目の和がKである時の場合の数を求めなさい
受験を思い出す問題ですが、これ受験に出したらまずそう()、そんな問題です
これは形式的べき級数を使わないと表すのが面倒くさいです
結論から言うとが答えです
これはaの目とbの目とcの目が出た時、和がa+b+cになる事を、
であることを用いて表しています
サイコロをN回投げます。出た目の和がKである確率を求めなさい
前問の式にを掛けてあげるだけです、
と出来るので、今後各項にを掛けた式を使っていきます
サイコロをN回投げます。出た目の和の和の期待値を求めなさい
いよいよ期待値に入って行きます!
出た目の和の確率分布はで表せる事を前問で確認しました
と置くと、
求めたいものは になります
これをは普通に掛けていってもいいのですが
であることに注目すると、
即ち
が求めたい期待値であることがわかりました!!!
期待値の和は和の期待値であることを形式的冪級数を用いて確認しなさい
実は前問、こんな複雑なことをせずとも、
1回あたりの期待値がなので
で十分です...
なぜなら期待値の和は和の期待値だからです...
期待値の和は和の期待値であることの説明はここにあります
mathtrain.jp
これが成り立つ事を形式的冪級数を用いて確認したいです
期待値の和は和の期待値であることの証明はしません
形式的冪級数で表せない事象においても期待値の和は和の期待値であるので、不可能です
では、行きます
確率母関数がである事象と確率母関数が
である事象、それぞれの期待値は先程と同様に
と
なので
その和、即ち期待値の和は
です
一方、形式的冪級数の性質から、は両者の和の母関数になります
なので、和の期待値はです
ここでに見えますが、
期待値の和は1なのでであり、
そのためが成り立ちます
よって少なくとも確率母関数がである事象と確率母関数が
である事象の間に期待値の和=和の期待値の関係を確認できました
N回振った時サイコロを出た目の和がK以上になる確率を求めなさい
上に上げたmaspyさんの記事を読んでるとわかりやすいです
まず、N回振った時サイコロを出た目の和がKである確率がの
の項であることを上で確認しました
これを使うと、
とおいた時、
が N回振った時サイコロを出た目の和がK以上になる確率になることがわかりますが、
なんと、を取り除く事ができます
ここで唐突に、とした時の、
の
の項を考えます
すると丁度になる事が分かるので、
に注意すると
が答えになる事がわかります
サイコロを出た目の和がK以上になるまで振った時の振った回数の期待値を求めなさい
最終問題です
これも形式的冪級数でかけます
N回振った時サイコロを出た目の和がK以上になる確率を使って、
これが答えになります
求まった!!!!
終わりに
いかがでしたでしょうか、最初は競プロやってない人向けにもわかりやすく書くつもりでしたが、最後のだけなんだかんだで難しくなってしまいました
形式的冪級数、こねこねしてるだけで楽しいので、皆もこねこねしてみてね
明日は53代はしどいさんの「君はイージングを知っているか!?」です
イージングとは何でしょうか!?
今から楽しみですね!