AGC028 B - Removing Blocks - ツバサの備忘録

解法

サンプル2がすごい実験に使いやすいのでこれを利用していくことで解けました。
まず、 $a_{i}$ は、 $i$ 番目が足される回数に最後に掛け合わせるだけでいいので、これ以降は無視をします。
ということで、 $i$ 番目の数字が何回足されるか、を調べます。
$memo[i][j] = i$ 番目の数字が、 $n!$ 回の試行において $j$ 番目を取り除いたときに何回足されるか
とします。
$memo[i][j]$ はもちろん $n!$ になります。
$i=1$ としてみます。
$j=2$ のとき、 $j$ より先に $i$ が取り除かれてはいけません。
このようなパターンは、ちょうど半分存在するので、
$memo[1][2] = \frac{n!}{2}$ になります。
$j=3$ のとき、 $3$ を取り除く前に、 $2$ と $1$ が先に取り除かれてしまってはいけないので、
1,2,3のブロックの順列を考えると、
123, 132, 213, 231, 312, 321 の6パターンのうち2パターンであったときのみ $3$ を取り除いたときに $1$ の数が足されます。
これは全体で $1/3$ なので、
$memo[1][3] = \frac{n!}{3}$ になります。
同様のことを考えると、
$memo[1][j] = \frac{n!}{j}$ になります。
$i$ が2以降のときを考えていく必要があるのですが、 $i$ より右側と左側はそれぞれ独立に考えてしまっても問題ありません。
なので、結局は、 $i=1$ と似たようなことが起きていて、
$memo[i][j] = \frac{n!}{|i-j|+1}$
という式が完成します。
あとはこの式の計算量を落とせば完成になります。
具体的には、 $memo[1][j]$ の総和を愚直に求めた後は、 $i$ が増えたときに先頭と末尾の2つの要素のみを入れ替えればいい(スライドしていくイメージです)ので、O(N)まで落とすことができます。
最後に、 $memo[i][j]$ の $i$ についての総和と、 $a_{i}$ の積をどんどん足していけば、答えが求まります。