第6回ドワンゴからの挑戦状予選 B問題メモ

なんかドワコンは毎回苦手意識がある。

B - Fusing Slimes

問題

数直線上にスライムが $N$ 体並ぶ
左から $i$ 番目のスライムは、整数座標 $x_i$ に位置する
以下の操作を $N-1$ 回繰り返し、スライムを1匹になるまで合成する
- 残っている中で右端の1匹を除くスライムを等確率で選ぶ
- 選んだスライムを、右隣のスライムの位置まで移動させて、合成して1匹にする
スライムの移動距離の総計の期待値に、$(N-1)!$ をかけた値を、$10^9+7$ で割った値を求めよ
$2 \le N \le 10^5$
$1 \le x_1 \lt x_2 \lt ... \lt x_N \le 10^9$

解法

解説pdfの確率を利用する方法がよりスマート。自分は別の考え方で解いて、複雑なだけで特に優れている点は無いが、一応メモしておく。

出力すべき値はややこしい書き方をされているが、要はスライムを選ぶ順番が全部で $(N-1)!$ 通りあり全て等確率なので、全ての選び順においての移動距離の総和を求めればよい。この「全ての選び順における移動距離の総和」を「総実現値」と呼ぶことにする。

1回の選び方ごとに移動距離を計算するのは難しいので、各隣接スライム間の距離を「区間」として、その区間が総実現値に何回足されることになるかを計算する。スライム $i～i+1$ の区間を $d_i$ と表す。

i  1   2   3   4   5   6    スライムのindex
     1   2   3   4   5      区間のindex
------------------------
x  1   3   6  10  15  21    スライムの位置
d    2   3   4   5   6      区間長

区間より左のスライムの考察

区間 $d_i$ を通る可能性のあるスライムは、$1～i$ に限られる。まずはこの $i$ 個のみの、全ての選び順における通過回数を考える。

スライム $i$ が選択された時に、はじめて $d_i$ を1匹のスライムが通過する。（それまでに他のスライムが選ばれていたとしても、どこかでせき止められている）

その時に区間の左側に残ったスライムの数を $k$ とすると、先ほどの1回に加え、あといくつのスライムが $d_i$ を通るか？

これは $k$ にのみ依存し、初期状態から区間 $k$ を通過するスライムの数と一致する。（ただし $k=0$ のとき 0）

😄  😄   😄    😄<---di--->🙂 ...

初手で選ばれたとき
😄  😄   😄     ・<---di--->🙂    残り3個 = 区間3を通るスライムの数と一致
↓
😄  😄   😄<--->                ←この通過回数と一致

いくつか合成されてから選ばれたとき
・   😄   ・     ・<---di--->🙂    残り1個 = 区間1を通るスライムの数と一致
↓
😄<-->・                         ←この通過回数と一致

よって $i$ が小さい方から、$d_i$ の総実現値への寄与回数を計算して、その結果を $R_i$ として記録しておくことで、動的計画法的に計算できる。

kを固定

スライムを左から選ばれた順に並べ、スライム $i$ が選ばれたときに左に $k$ 個残っている場合に、$d_i$ が何回通過されるか（総実現値への $d_i$ の寄与回数）を考える。

|-------------------|  i個
○ ... ○ i ○ ... ○
|-------|   |-------|
 i-k-1個       k個

スライム $i$ 以外の $i-1$ 個の左右への振り分け方は ${}_{i-1}C_k$ 通り。

左側の（先に選ばれた）スライムの並び順は $(i-k+1)!$ 通り。

右側のパターン数は $R_k$ に包含されているので考えなくてよいが、区間 $d_i$ 自体の寄与回数は、残る $k$ 個の選び順のパターン数だけ“1”が加算されるので、 $R_k+k!$

これらを掛け合わせて、$\displaystyle {}_{i-1}C_k(i-k+1)!(R_k+k!) = \frac{(i-1)!}{k!}(R_k+k!)$ となる。（あくまで $d_i$ より左のスライムのみに限定した場合）

kの総和

今までは $k$ を固定して考えていたが、$k=0～i-1$ までの値を取るので、この総和を取ったものが $d_i$ の寄与回数となる。（あくまで $d_i$ より左のみ）

$\displaystyle \sum_{k=0}^{i-1}\frac{(i-1)!}{k!}(R_k+k!) = (i-1)!\sum_{k=0}^{i-1}\frac{R_k+k!}{k!}$

これをこのまま計算すると各 $i$ の中で $k$ のループが回るので $O(N^2)$ だが、$\sum$ 内は $k$ のみに依存するので、新しい $R_i$ が求められるたびに $\displaystyle \frac{R_i+i!}{i!}$ を加算していけば、毎回ループを回さなくても計算できる。

区間より右のスライム

さて、これまでで区間より左に限定したスライムの寄与回数が決まったが、ここに区間より右のスライムの選び方を乗じる必要がある。

区間より右の $N-i$ 個のスライムは、いつ選ばれようと、区間 $d_i$ の加算数に影響することは無い。

つまり、区間より左 $i$ 個の選び順の、$i+1$ 箇所の好きな位置に、どのような順番で挟み込んでもよい。

v  v  v  v  v
 ○ ○ ○ ○

よって、どの位置（v）に何個入れるかで ${}_{i+1}H_{N-i}$ 通り、その時の並び順で $(N-i)!$ 通り、あわせて $\frac{N!}{i!}$ 通りとなる。

まとめ

$R_0=0$ として、$\displaystyle dp[i]=\sum_{k=0}^{i}\frac{R_k+k!}{k!}$、つまり $dp[0]=1$ とする。

左の区間から、その区間の総実現値を計算していく。

区間 $d_i$ の総実現値への寄与は $\displaystyle d_i \times (i-1)! dp[i-1] \times \frac{N!}{i!}$ となるので、これを足し合わせていく。

同時に $\displaystyle dp[i]=dp[i-1]+\frac{(i-1)! dp[i-1] + i!}{i!}$ として次の区間の計算に備える。

def prepare(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return factorials, invs


n = int(input())
xxx = list(map(int, input().split()))
MOD = 10 ** 9 + 7
factorials, invs = prepare(n, MOD)

ans = 0
dp = 1
for i in range(n - 1):
    cur = dp * factorials[i] % MOD
    ans = (ans + (xxx[i + 1] - xxx[i]) * cur * invs[i + 1]) % MOD
    dp = (dp + (cur + factorials[i + 1]) * invs[i + 1]) % MOD
ans = ans * factorials[n - 1] % MOD
print(ans)

目次

第6回 ドワンゴからの挑戦状 予選 B問題メモ