第6回ドワンゴからの挑戦状予選 - B - Fusing Slimes - Senの競技プログラミング備忘録

atcoder.jp

概要

N個のスライムがあり、それぞれの位置はx[i]である。次の操作をN-1回行う。

残ってるスライムのうち、一番右を除いたのを等確率で1つ選び、それを一つ右に相当するスライムのところまで移動する。そして、その2つのスライムを合体させて1つのスライムとする。

このN-1回の操作によるスライムの移動距離の総和の期待値を求めよ。

制約： 1 <= N <= 10^5, 1 <= x[1] < x[2] < ... < x[N] <= 10^9

ACするまで

これから以降、Xの添え字は、スライムの合体によってずれることはなく、Xとして与えられたの順番を参照するものとする。

1. 期待値かぁ。総和だし期待値の線形性をからめられるかを考えてみるか。
2. [i, i + 1]を通る個数の期待値、と問題を言い換えられる。ここまで40分経過。
3. 計算のやり方が分からない・・・。コンテスト終了。

4. 区間[i, i + 1]を通る個数の期待値自体は、X[i], X[i - 1], X[i - 2],..X[1]がそこを通る確率の和と同じ。これで部分点。
5. X[k]が[i, i + 1]を通る確率、というサブ問題を解くと、有名な級数ができる。最終的に答えとなる数式を見ると、前処理をすることで次元が落ちてAC。->AC!

考察

まず、「通った距離の総和」の期待値を、期待値の線形性を使って、「[i, i + 1]を通ったスライムの数の期待値」を全区間分たしたものに言い換える。

つまり、次のサブ問題１を解ければよい。

[i, i + 1]を通ったスライムの数の期待値を、iごとに求められるか？

区間[i, i + 1]で、通る可能性のあるスライムは、1, 2, ..., i - 1, i番目しかない。
i番目は、必ず通るので、数の期待値は+1される。では、それ以外はどうなるのだろうか？
実験してみると、i-1番目が通るには、先にi番目のスライムが動く必要があり、i-2番目が通るには、先にi-1, i番目のスライムが動く必要があるとわかる。
つまり、
p(< i)番目が[i, i + 1]を通るには、p番目が選ばれる前に、i, i -
1, ..., p + 1番目がすでに選ばれてる必要がある

ここで、また別のサブ問題２が芽生える。

長さKの順列をランダムで1つもってくる。1 <= a[1] < a[2] < ... < a[l] <= Kとして、その順列の中でa[l]より先に、a[1], a[2], ... , a[l - 1]がこの順番でなくとも、すべてすでに現れてる確率は？

この問題が解ければ、さきほどのつまりの部分は求まり、この問題もACできるだろう。(計算量はさておき)

この問題は、こうやって考えるとわかりやすい。
$K!$ 個ある順列のうち、l個のaにかかわる値の並びだけを見ると、 $l!$ 通り存在する。そのうちで、a[l]が最後に現れると決まってる時、一番後ろはa[l]で1通りだが、その前のl - 1個の並びは任意でよいので、 $(l-1)!$ 通りの条件を満たす並びができ、 $\frac{1}{l}$ の確率でこれが成り立つとわかる。これは、すべての並び方、つまり $K!$ 通りのうちでも、 $\frac{1}{l}$ の確率a[l]がaの中の最後に来るとわかる。