AGC028-B: Removing Blocks - 思考の墓場

数え上げ力の不足。

問題概要

1から $N$ までの番号がついたブロックが横にならんでおり，ブロック $i$ には重さ $A_i$ がある。ここから $N$ 回ブロックを取り除くのだが，ブロック $i$ を取り除くコストはブロック $i$ と連結な(自身も含む)ブロックの重みの総和である。取り除く順番は $N!$ 通りあるが，それらのコストの総和を求めよ。

問題リンク:

B - Removing Blocks

解法

この手の問題は，「 $A_i$ が何回加算されるか？」ということを考えるのが定石である(そこまではわかる，という人が多かったと思う)。特にこの場合は，「ブロック $j$ を取り除いたときに $A_i$ が加算されるのは何回か？」ということを考えればよい。各 $j$ についてこれを足し合わせれば「 $A_i$ が何回加算されるか？」という問いの答えがわかる(ここまではよかった)。

では，「ブロック $j$ を取り除いたときに $A_i$ が加算されるのは何回か？」という問いを考えよう。簡単のため， $j\leq i$ とする。公式解説では確率を用いているが(これはこれで賢い)，実は確率を持ち出さなくても十分である。ブロック $j$ を取り除いたときに $A_i$ が加算されるためには，ブロック $j$ を取り除くまでに，ブロック $j$ からブロック $i$ までが取り除かれなければよい。そのような順列はいくつあるかを考える。
$i-j+1=k$ とおこう。これら $j$ から $i$ の $k$ 個の数の並べ方のうち， $j$ が一番最初になるのはもちろん $(k-1)!$ 通りである。これを1から $N$ の順列に埋め込むことを考える。埋め込む位置の選び方は， $N$ 箇所から $k$ 箇所選ぶ場合の数なので， ${}_N \mathrm{C} _k$ 通りである。 $j$ から $i$ 以外の数字の並べ方は任意でよいので， $(N-k)!$ 通りある。以上より，「ブロック $j$ を取り除いたときに $A_i$ が加算されるのは何回か？」という問いの答えは， $(k-1)! \times {}_N \mathrm{C} _k \times (N-k)! = \frac{N!}{k}$ とわかった。
$i \lt j$ のときも同様に考えて同じ表式を得る。あとは， $\frac{1}{k}$ の累積和を事前に計算すれば，「 $A_i$ が何回加算されるか？」という問いに $O(1)$ で答えることができる。よって，全体で $O(N)$ で計算ができる。

提出

Submission #3403177 - AtCoder Grand Contest 028

これが解けなかったのは悲しい。