某所で話題になった問題を調べていたらおもしろかったので紹介します。
問題文
数列 ( ) の 美しさ を、隣り合う 2 項の組であって、 差の絶対値が d であるものの個数として定義します。 例えば、d=1 であるとき、数列 (3,2,3,10,9) の美しさは 3 です。各要素が 1 以上 n 以下の整数である長さ m の数列は全部で nm 通り存在します。 この nm 通りの数列すべてに対して美しさを求めて、 それらの平均を出力してください。
制約は、0≤d<n≤10^9 2≤m≤10^9 入力はすべて整数
ここで隣り合う2項はm-1通りあるので期待値の線形性を利用し、m-1通りそれぞれについて差がdである確率を求めてすべて足すと答えが求まるというもの。
なるほどわからん。
期待値の線形性
サイコロでのたとえがわかりやすかった。 サイコロを1回振った時の出目の値の期待値は7/2。これは出目の合計を6で割ることですぐに求まる。けど2回振った時の値の和の期待値を求めるには？を考える。
単純に行くと出目の組み合わせを36通り考えて計算をする必要があるが、和の期待値は期待値の和であることを利用すると、 一回振った時の期待値＝7/2なので、2回振った時の和の期待値は単純に×２するだけ、よって答えは7になる。と考えることができるらしい。
もちろん∑をつかった公式があるけれど、言葉で直感的に納得できる公式って面白いなと思った話でした。明日は問題についてすこし考えてみます。
