続きです。けりを付けます。相変わらず適当なこと言ってるかもしれません。
問題文
数列 ( ) の 美しさ を、隣り合う 2 項の組であって、 差の絶対値が d であるものの個数として定義します。 例えば、d=1 であるとき、数列 (3,2,3,10,9) の美しさは 3 です。各要素が 1 以上 n 以下の整数である長さ m の数列は全部で nm 通り存在します。 この nm 通りの数列すべてに対して美しさを求めて、 それらの平均を出力してください。
制約は、0≤d<n≤10^9 2≤m≤10^9 入力はすべて整数
数列の美しさの期待値を求める
いざ期待値を求めるとなるとわからないことが多いです。普通のやり方ならばすべての数列の美しさを調べ、その合計をnmで割れば求まります。ですが、すべての数列の美しさを調べていたらプログラムといえど時間がかかります。間違いなくジャッジはTLEでしょう。
でもいろいろ調べた結果、考え方はまとまったので備忘録として残します。
確率と期待値とインディケータ確率変数
まず、数列の美しさ(個)を確率変数とします。確率変数とは試行で得られる値のこと。サイコロなら出目、今回の場合は美しさなど、自由に定義できます。確率変数の期待値の定義は確率変数の平均値のことなので題意に沿っているのはわかると思います。
ここで新しく確率変数を考えます。隣り合う２項がdに等しい場合に１、等しくない場合に０になる確率変数です。このような確率変数をインディケータ確率変数といいますが、この確率変数の期待値はどうなるでしょうか。
定義より、この確率変数の期待値は「隣り合う２項がdに等しい整数のペアの個数」を「整数ペアのすべての組み合わせ(=n2)」で割ったものになります。これは実際にどんなものか見てみます。
「隣り合う２項がdに等しい整数のペアの個数」を考えます。
d=0の場合は、2つの整数が等しい時です。つまりn個になります。(1,1),(2,2)...(n,n)ですね。
d=1の時は、nとn-1、またはn-1とnのパターンが考えられます。これはわかりにくいですが、nの取りうる値より１小さい数が存在するペアなので、片方で(n-1)個、入れ替えのパターンがあるので2(n-1)個になります。
さらにdが2,3...と増えていくときもd=1のときと同じ考えなので、0<dのとき、2(n-d)個となります。
つまり新しく作った確率変数の期待値は以下のようになります。
d=0のとき、n/n2
d<0のとき、2(n-d)/n2
なんか確率みたいな値がでてきました。実際にこれは確率を示しています。どんな確率かというと、が1となるような確率です。ですが上のほうで定めた通り紛れもなく期待値でもあります。
また、は隣り合う２項について定義されているのでm-1個存在します。最初の2項については
と表せますが、どんな2項でも差の絶対値がdと等しい確率は同じなので定義もまったく一緒です。
まとめ
話を戻します。求めたいのはの期待値でした。これは期待値の線形性から
と以下のような関係になります。
( +
+ ... +
+ ... +
)の期待値 =
の期待値
さらには確率として問題文より計算できる状態です。ようやく答えが見えました。dが0かそれ以上の場合分けをし、確率をもとめた上でそれがm-1個あるのでこの総和を計算します。それぞれの確率は同じなので、単にm-1倍しても良いでしょう。これが期待値の和であるため、和の期待値である
と求めるべき答えになります。
余談
インディケータ確率変数というワードで気づく方もいるかもしれませんが(一般的にはベルヌーイ確率変数)、この考え方は書籍「数学ガール 乱択アルゴリズム」にでてくる2項分布の説明を焼き直したものです。とくにインディケータ確率変数の期待値はインディケータ確率変数が1になる確率に等しいということがこの問題のポイントだと感じました。でもあってるんですかねこれ......？聞きかじりの知識をつなげるのはこれが限界...と言い訳しておきます。
- 作者: 結城浩
- 出版社/メーカー: SBクリエイティブ
- 発売日: 2011/02/26
- メディア: 単行本
- 購入: 19人 クリック: 779回
- この商品を含むブログ (103件) を見る
