No.352

愚直にやると $N!$ の組み合わせがあるのでまったく間に合わない. そこで, $i$ 枚のカードが並んでいるときに $i+1$ のカードを追加するときのコストの期待値を考える.

まず, $i$ 枚カードが並んでいるときに $i+1$ のカードを $j$ 枚目と $j+1$ 枚目の間追加するときにかかるコストを考える.

$j$ 枚目が $a$ で $j+1$ 枚目が $b$ のときにコスト $ab$ がかかる. そして, $j$ 枚目が $a$ で $j+1$ 枚目が $b$ になる組み合わせの数は, $(i-2)!$ 通りになる.

また, $i$ 枚のカードが並んでいるときに $i+1$ のカードを両端に追加する組み合わせの数は $2 \cdot i!$ である.

よって, $i$ 枚のカードが並んでいるときに $i+1$ のカードを追加するときのコストの期待値 $E(i)$は,

$$\begin{align} E(i) &= \frac{2 \cdot i! + \sum_{j=1}^i \sum_{a=1}^i \sum_{b=1, a \neq b}^i (i-2)!ab}{i!(i+1)} \\ &= \frac{2 \cdot i! + \sum_{a=1}^i \sum_{b=1, a \neq b}^i (i-1)!ab}{(i+1)!} \\ &= \frac{2i + \sum_{a=1}^i \sum_{b=1, a \neq b}^i ab}{(i+1)i} \end{align}$$

となる.

あとは $1 + \sum_{i=1}^{N-1} E(i)$ を計算すればいい.