目次
文書の過去の版を表示しています。
第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!)$
これは、$k=0$ から、新しい $R_i$ が求められるたびに $\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 = d_i \times (i-1)! dp(i-1) \times \frac{N!}{i!}$ となる。
$dp(i)=dp(i-1)+\frac{D_i + 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)