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

#期待値

1. スライム i, i + 1 の間の距離が何回足されるか
方法 3 通り
1.1. 漸化式
1.2. 各々のスライムに対して何回通るかの確率を考える
1.3. 再帰的に解く

2. スライム i, j の間の距離が何回足されるか

editorial
https://img.atcoder.jp/dwacon6th-prelims/editorial.pdf

editorial の補足

1 indexed とする
$\forall$ i (1 ≤ i ≤ N - 1) に対し, i 番目のスライムと i + 1 番目のスライムの距離が何回足されるか考える

各単位部分が何回足されるか考えるのは本当によくある
シグマの入れ替え問題とか

4
1 2 3 5

距離は各々 1, 1, 2

スライム 1 , スライム 2 の間の 1 が何回足されるか

スライム 2 , スライム 3 の間の 1 が何回足されるか

(i) スライム 1 → スライム 2, スライム 2 → スライム 3
(ii) スライム 2 → スライム 3, スライム 1 → スライム 3

よって, 確率 $\frac{1}{2}$ で 1 が 1 回, 確率 $\frac{1}{2}$ で 1 が 2 回足される

スライム 2 , スライム 3 の間の距離が足される回数の期待値は, $\frac{1}{2}$ * 1 + $\frac{1}{2}$ * 2 = $\frac{3}{2}$

スライム 3, スライム 4 の間の 2 が何回足されるか

問題文通りに実験
(i) 1 → 2, 2 → 3, 3 → 4
(ii) 1 → 2, 3 → 4, 2 → 4

(iii) 2 → 3, 1 → 3, 3 → 4
(iv) 2 → 3, 3 → 4, 1 → 4

(v) 3 → 4, 1 → 2, 2 → 4
(vi) 3 → 4, 2 → 4, 1 → 4

スライム 3, スライム 4 の間の距離が足される回数の期待値は, $\frac{1}{6}$ * 1 + $\frac{1}{6}$ * 2 + $\frac{1}{6}$ * 1 + $\frac{1}{6}$ * 2 + $\frac{1}{6}$ * 2 + $\frac{1}{6}$ * 3 = $\frac{11}{6}$

実は, スライム i, スライム i + 1 の間の距離が足される回数の期待値は,
1 + $\frac{1}{2}$ + ... + $\frac{1}{i}$

1, $\frac{3}{2}$ , $\frac{11}{6}$ をオンライン数列大辞典 (OEIS) に投げれば出てくる

先の例
4
1 2 3 5
の答えは
1 * 1 + 1 * $\frac{3}{2}$ + 2 * $\frac{11}{6}$

1 + $\frac{1}{2}$ + ... + $\frac{1}{i}$ の求め方

f:id:tac_12:20200111233319p:plain:w300
(youtube の editorial より)

$C_n$ : 区間 i, i + 1 を通過するスライムの個数の期待値

スライム 1 ~ i が, 区間 i, i + 1 を通過する可能性を持つ

(i) スライム i が最初に移動する場合
f:id:tac_12:20200112142018p:plain:w300
スライム i は区間 i, i + 1 を通過し, 残りのスライムに対しては $C_{n - 1}$ と同じ状況

(ii) スライム 1 ~ (i - 1) のいずれかが最初に移動する場合
それらが移動しても 2 ~ i のいずれかと合体するだけで, 区間 i, i + 1 を通過しない
そして, 残りのスライムに対しては $C_{n - 1}$ と同じ状況

editorial (pdf) の補足

$C_i$ = 1 + $\frac{1}{2}$ + ... + $\frac{1}{i}$ の別の求め方
個々のスライムについて見る

$x_{i + 1} - x_{i}$ が足される回数の期待値は, 各々のスライムがそこを通過する確率の和に等しい

スライム k (k ≥ i + 1) は確率 0

スライム i は確率 1

スライム i - 1 は, 先にスライム i がスライム i + 1 のとこに行ってたら, スライム i, i + 1 間を通る
よって, 確率 $\frac{1}{2}$

スライム i - 2 は, 先にスライム i, i - 1 がスライム i + 1 のとこに行ってたら, スライム i, i + 1 間を通る
よって, 確率 $\frac{2}{3} * \frac{1}{2}$ = $\frac{1}{3}$
スライム i, i - 1 のどちらかを最初に選び, 次に, その選んでない方を選ぶ

スライム i - 3 に関しても同様に,
$\frac{3}{4} * \frac{2}{3} * \frac{1}{2} = \frac{1}{4}$
となる

別解

#期待値dp #挿入dp

Fusing Slimes [Dwango Programming Contest 6th B] - はまやんはまやんはまやん

補足

重要
はまやんさんの記事では数列が 132 なら, 2, 3, 1 の順に移動するが, 本記事では 1, 3, 2 の順に移動する

スライムが 8 体あるとする
スライム 7, 8 間の距離が何回足されるか

移動するスライムが 5, 7, 2, 6, 3, 4, 1 の順だとする
5 → 6 : 足されない
7 → 8 : 足される
2 → 3 : ×
6 → 8 : ⚪︎
3 → 4 : ×
4 → 8 : ⚪︎
1 → 8 : ⚪︎
計 4 回

まず, スライム 7 が移動するまで足されない
次, スライム 6が移動するまで足されない
...

スライム 7, 8 間の距離が何回足されるか
スライム 7, 6, 4, 1 が移動したとき

6 の次 4 なのは, すでに 5 は 4 に行ってるから
4 の次 1 なのは, 4 が移動する時点ですでに 2 → 3, 3 → 4 だから

1. スタートは, 移動するスライムの数列 5726341 の最大の数 7
2. 次に移動するのは, 7 の右の, 一番大きい数 6
...

以上は, スライムが 8 体ある場合の, 数列 5726341 の場合

1234567, 2356741 とか, 他のすべての数列も考える

再帰的に解けないか

dp[i] := i 個の順列を並び替えた全通りについての, スライム i, i + 1 間を通るスライムの個数の期待値

f:id:tac_12:20200112155807p:plain

dp[i] = (dp[0] + 1) / i + (dp[1] + 1) / i + (dp[2] + 1) / i + (dp[3] + 1) / i + ... + (dp[i - 1] + 1) / i

/ i の理由
挿入箇所は等確率で選ばれる

+ 1 の理由
f:id:tac_12:20200114232456p:plain:w300

書き出してみる

dp[0] = 0
数列がない

dp[1] = (dp[0] + 1) / 1 = 1
数列がないとこには, 1 を置くだけ
(挿入箇所は 1 箇所)
確率 1 で 1 箇所に挿入

dp[2] = (dp[0] + 1) / 2 + (dp[1] + 1) / 2 = $\frac{3}{2}$

別解 2

第6回ドワンゴからの挑戦状予選 : B - Fusing Slimes - kmjp's blog

補足
スライム i が, ちょうどスライム j まで移動する確率
スライム i, j 間の距離に注目してることになる

(i) スライム j が最も右, すなわち j = N のとき
スライム i より右のスライムすべてが, スライム i より先にスライム j のとこへ行く
そうすれば, スライム i はスライム j - 1, j 間を移動できる

確率は, $\frac{j - i - 1}{j - i} * ... * \frac{2}{3} * \frac{1}{2} = \frac{1}{j - i}$
まず, スライム i ~ (j - 1) のうち, スライム i 以外から選ぶ
次に, スライム i 以外の残りから選ぶ
...

j = N より, $\sum_{i}^{} \frac{1}{N - i}$

(ii) j $\neq$ N のとき, すなわち, スライム j がいつか移動するとき
i ~ j のうち, j が最後に移動する
そうでないと, j のとこでとまれない

i ~ (j - 1) で, i が最後に移動する

もう一度
i ~ j で, i, j 以外をすべて選ぶ
次に, i を選ぶ
最後に, j を選ぶ

$\frac{j - i - 1}{j - i + 1} * \frac{j - i - 2}{j - i} * \frac{j - i - 3}{j - i - 1} * ... * \frac{3}{5} * \frac{2}{4} * \frac{1}{3} * \frac{1}{2}$

最初の方をもう少し延ばしてみる
f:id:tac_12:20200112171617p:plain:w300

$\frac{1}{(j - i + 1)(j - i)}$ だけ残りそう #ques

後ろの方をもう少し延ばしてみる
f:id:tac_12:20200112171630p:plain:w300

$\sum_{i}^{} \sum_{j ≥ i + 1}^{}$ (X[j] - X[i]) $\frac{1}{(j - i + 1)(j - i)}$

$\sum_{i}^{}$ の中身
$\sum_{j ≥ i + 1}^{}$ X[j] $\frac{1}{(j - i + 1)(j - i)}$ - X[i] $\sum_{j ≥ i + 1}^{} \frac{1}{(j - i + 1)(j - i)}$

各々, 累積和で計算する

本番で何をやってたか

区間 i, j を決めたとする
(i, k), (k, j) に分けて部分問題にできないか
とりあえず, 計算量は置いといて

重複なく, 漏れなくできるか?
できない
sample 1
3
1 2 3 5
で,
(以下, 数字はスライムの番号)
(1, 2), (2, 4) から
1 → 2, 2 → 3, 3 → 4 が作れるし,

(1, 3), (3, 4) からも
1 → 2, 2 → 3, 3 → 4 が作れる

区間 i, j が足される回数や, 区間 i, i + 1 が足される回数を考えようとするも, わからなかった

1 → 3, 2 → 3 とかはない
ありうるものをまとめられなかった

i の左や j の右はどうすんのってなった
区間 i, i + 1 に関して考える場合, スライム i, i-1, i-2, ... の順に見ればよかった