2020年1月11日土曜日

第6回 ドワンゴからの挑戦状 予選 B - Fusing Slimes

求めるのは(N−1)!(N-1)!通りの移動に関する距離の総和である。

f(p,q):=xpf(p, q) := x_pからxqx_qへの移動による距離の総和、とする。この移動が起こるのは、スライムp+1,...,q−1{p+1}, ..., {q-1}が自由な順番で選ばれ、そのあとでppが選ばれ、さらにそのあとでqqが選ばれるケースである。この選び方を数えると、N−1N-1箇所の中からq−p+1q-p+1箇所を選び、その中の始めのq−p−1q-p-1箇所にスライムp+1,...,q−1p+1, ..., q-1を自由な順番で配置し、末尾の2箇所にスライムp,qp, qを配置し、残ったN−1−(q−p+1)N-1-(q-p+1)箇所に残りのスライムを自由に並べればよい。つまり、

f(p,q)=(N−1q−p+1)(q−p−1)!(N−1−(q−p+1))!×(xq−xp)=(N−1)!(q−p+1)(q−p)(xq−xp) \begin{aligned} f(p, q) & = \binom{N-1}{q-p+1}(q-p-1)!(N-1-(q-p+1))! \times (x_q-x_p)\\ & = \frac{(N-1)!}{(q-p+1)(q-p)}(x_q-x_p) \end{aligned}

ただし、q=Nq = Nの場合はスライムqqが選ばれないので

f(p,q)=(N−1N−p)(N−p−1)!(N−1−(N−p))!×(xN−xp)=(N−1)!(q−p)(xN−xp) \begin{aligned} f(p, q) & = \binom{N-1}{N-p}(N-p-1)!(N-1-(N-p))! \times (x_N - x_p) \\ & =\frac{(N-1)!}{(q-p)}(x_N - x_p) \end{aligned}

となる。ffの総和を単純に計算すれば部分点が取れる。

上の式でxq−xpx_q-x_pに掛かる係数は幅q−pq-pのみによって決まっているので、同じ幅について（q≠Nq \neq Nの場合に関して）整理してみる:

∑p=1N−1∑q=pN−1f(p,q)/(N−1)!=12⋅1(x2−x1)+...+12⋅1(xN−1−xN−2)+13⋅2(x3−x1)+...+13⋅2(xN−1−xN−3)+..+1(N−1)⋅(N−2)(xN−1−x1)=12⋅1((x2+x3+...+xN−1)−(x1+x2+...+xN−2))+13⋅2((x3+x4+...+xN−1)−(x1+x2+...+xN−3))+...+1(N−1)⋅(N−2)(xN−1−x1) \begin{aligned} & \sum_{p=1}^{N-1}\sum_{q=p}^{N-1}f(p, q)/(N-1)! \\ = &\frac{1}{2\cdot 1}(x_2-x_1) + ... + \frac{1}{2\cdot 1}(x_{N-1}- x_{N-2})\\ & + \frac{1}{3\cdot 2}(x_3-x_1) + ... + \frac{1}{3\cdot 2}(x_{N-1}- x_{N-3}) \\ & + .. \\ & + \frac{1}{(N-1)\cdot (N-2)}(x_{N-1}-x_1) \\ = &\frac{1}{2\cdot 1} \bigl( (x_2+x_3 + ... + x_{N-1}) - (x_{1}+x_2 + ... +x_{N-2}) \bigr )\\ & + \frac{1}{3\cdot 2} \bigl( (x_3+x_4 + ... + x_{N-1}) - (x_1 + x_2 + ... + x_{N-3}) \bigr) \\ & + ... \\ & + \frac{1}{(N-1) \cdot (N-2)}(x_{N-1} - x_1) \\ \end{aligned}

（(N−1)(N-1)!は共通なので除いて整理した。） これは累積和で処理できる形になっている。

満点に達するのに3時間かかった。解説の方針のほうが確かにずっと明快だけれど、上の整理くらいはさっさとできるようになりたい。

投稿者