しらとりのブログ

社会人ひよこプログラマのtil

競プロの問題を考える(期待値の線形性)

昨日の続きです。ただしく理解できているかあやしいですが、脳内を公開しておきます。

silatori.hatenablog.com

問題文


数列 ({\displaystyle a_1, ... a_n} ) の 美しさ を、隣り合う 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通りの数列を1つ1つ調べて隣り合う 2 項の差を計算するのは流石に時間がかかりそうです。(nm*(m-1)回の計算?爆発していることには違いない)
答えを言ってしまうと、ここで隣り合う2項の差がdになる確率を求めて、それをm-1倍したのもが答えになるそうです。why。

今回求めるものは期待値

今回求めるものは「nm通りの数列の美しさの平均値」です。つまり、「制約下での数列の美しさの期待値」です。 ですが、nm個の数列の美しさの値を調べるのは時間がかかりすぎるため出来ません。

明日は問題について考えてみます。