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

Dwango Programming Contest 6th

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

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$ が等しければ（$i$ など他の値に依らず）同じになり、初期状態から区間 $k$ を通過するスライムの数と一致する。（ただし $k=0$ のとき 0）

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

よって、$i$ が小さい方からその区間を通るパターン数を計算して、その結果を $R_i$ として記録しておくことで、動的計画法的に計算できる。

kを固定

スライムを選ばれた順に並べると、

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

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

先に選ばれたスライムの並び順は $(i-k+1)!$

この時の通過数は、残る $k$ 個の通過数に加え、$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=0～i-1$ までの値を取るので、この総和を取ったものが $d_i$ の総通過数となる。（あくまで $d_i$ より左の…以下略）

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

これは、新しい $R_i$ が求められるたびに $\displaystyle \frac{R_i+i!}{i!}$ を加算していけば、毎回 $\sum$ のループを回さなくても計算できる。

区間より右のスライム

さて、これまでで、区間より左のスライムの選び順が決まった。

区間より右の $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$ の答えへの加算は、$d_i \times (i-1)! dp(i-1) \times \frac{N!}{i!}$ となる。

$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問題メモ