AGC028 B. Removing Blocks

問題

1～Nの番号が書かれた箱が1列に並べてあり、各箱の重さは整数A_iで与えられる。
この箱を一つずつ取り除いていくことを考える。
ある箱を取り除くときのコストは、その両隣に連続している箱の重さの総和になる。
取り除き方はN!通り考えられるが、そのすべての取り除き方について、N回の取り除くコストの総和の合計を求めよ。

制約

• 1 <= N <= 10^5
• 1 <= A_i <= 10^9

解法

各箱について取り除かれる回数e_iがわかれば「Σ e_i * A_i」で求められる。
制約的にこの計算をO(NlogN)以下の計算量で行う必要がある。

(気付くのが厳しいが、)全事象を考えているので、確率的に考えて期待値を求めることでこのe_iを求める。

ある箱jが取り除かれるとき注目している箱iが連結している確率p_ijが求められれば、その期待値は「N! * Σ_{j=1}^N p_ij」で求められる。
jとiが連結している確率p_ijを考えると、iからjまでの連続した箱のうち、jが最初に選ばれる確率と同じであるので、p_ij = 1 / (abs(i-j)+1)と求められる。

今、MODで計算しているため、p_ijは逆元を計算しておけば整数値になる。
さらに、Σp_ijを考えるとき、p_ijは1/1+1/2+1/3+...のように連続した和になるので、累積和を求めておけばO(1)で求められる。

したがって、e_iがO(N)で求められ、Σe_i * A_iもO(N)で求められるので、全体でO(N)で求められる。

反省

DPや法則性の方向で考えてしまっていたので、確率・期待値の発想がまったく考慮できていなかった。
p_ijの形も解説のようにすぐ導出できなかったので、確率・期待値問題の練習がかなり必要・・・