SoundHound Inc. Programming Contest 2018 -Masters Tournament- B - Removing Blocks
N!の総和系なので、確率・期待値でやるべき問題。
まずは1回のコストの期待値を考える。答えはこれにN!をかけてやればよい。すると、ブロックj を取り除いたときに、ブロックiが連結である確率をP(i, j)としたとき、1回のコストの期待値はΣa[i] * P(i, j) となる。iを固定した時、Σ(a[i] * ΣP(i,j)) であるから、ΣP(i, j) のjに対する総和が求まればよい。
ブロックjを取り除いたときにiが連結になる確率が一番の肝であるが、これは区間[i, j]の中で一番最初に取り除かれるブロックがjである、という確率に等しい。これが最重要でここでハマる可能性が高い。
これさえわかればあとは簡単で、P(i, j) = 1 / (1 + | i - j |) であることがわかるので、これを計算し、ΣP(i, j) ( ただしjに関する和）が求まる。
期待値、確率系の問題では愚直に！やnCrを用いて書き下すのも重要だが、部分的に切り出して感覚的に明らかな確率に落とし込むというのも重要。
私は最初連結であるという確率を「(区間1) i (区間２) j (区間３)」という３区間に分け、nの順列を考えたときに(区間2)に相当する部分がiやjより後ろにある、という計算をしてハマってしまった。
