blogskol

思わず声に出して読みたくなるブログ

B - Fusing Slimes

1-indexedで書いてるからね

B - Fusing Slimes

言い換え

期待値大嫌いなので問題から期待値要素を消そうね

これは典型なので天才部分ではないです

ある程度強い人は自明パートなので飛ばして

離散事象の期待値は、重複を許して事象を全部等確率のものとして列挙した時に、 $\frac{全通りの総和}{通り数}$ と言えることが多い（総和ってのは今回でいうとスライムの移動距離の合計のこと）（なんかそもそも期待値をこっちの定義で覚えてる人もいそう）

で、今回はこの分母が $N-1$ 体のスライムを選ぶ順番の通りなので $(N-1)!$ なんですが、この問題では優しいことに最後に $(N-1)!$ をかけるので、求めたいのは分子そのもの

つまり、起こりうる事象 $(N-1)!$ 通りそれぞれでのスライムの移動距離の総和を求めればいいです

こういう風に期待値の問題を全事象の総和を求める問題に言い換えるのは典型で、逆に総和を求める問題を期待値の問題に言い換えることもある

多分この辺他の人の記事読んだ方がわかりやすいんだよね

考察

当たり前だけど $(N-1)!$ なんて全部計算していられない

で、こういうのは「各区間について、その区間の移動が行われるのは何通りか」を出して足し合わせるのが典型（まぁなんかどこがまとめて計算出来るのかみたいなのを考えるのが大事）

なるべく一般的な計算式が欲しいので、とりあえず $i$ 番目のスライムが $i+j$ 番目のスライムにくっつくのが何通りあるか数えてみて、（つまり、 $x_{i+j}-x_{i}$ が何回足されるか）これを $f(i,j)$ とおくと、

　 $j-1$ 体のスライム-> $i$ 番目のスライム-> $i+j$ 番目のスライム

の順番だけ決まっているので、

　 $f(i,j)=nCk(N-1,j+1) \times (N-1-(j+1))! \times (j-1)!$

ただし $i+j=N$ の時は右端が消えないことが確定しているのでこの場合は

　 $g(i,j)=nCk(N-1,j) \times (N-1-j)! \times (j-1)!$

よくみると $f(i,j),g(i,j)$ は $i$ が式中に含まれないから $f(j),g(j)$ だねとなる

まとめると、

　 $\sum_{j=1}^{N-2}f(j) \sum_{i=1}^{N-1-j} (x_{i+j}-x_{i})+ \sum_{j=1}^{N-1}g(j) (x_{N}-x_{N-j} )$

が答え

　 $\sum_{i=1}^{N-1-j} (x_{i+j}-x_{i})$ 　

の部分はグッと睨んだり図を書くと相殺が起こって、

　 $\sum_{i=N-j}^{N-1} x_{i} - \sum_{i=1}^{j}x_{i}$

になるので累積和で前計算出来て解けた〜

なんか添字間違ってそうだし計算式そのまま写さないで自分で考えて書いてね

コード

Submission #9433719 - Dwango Programming Contest 6th

42行目まではnCk作ったり雑なmodintなので、43行目から読めばいいと思う

記事そのままだからあんまり見ても仕方ない感あるけど