あらかじめ \(A\) をソートし、 \(A_1 \le A_2 \le \dots \le A_N\) とする。

部分点1 \((N \le 500)\)

\(dp[i][j] = \) 人 \(i\) から人 \(j\) までを座らせるときのスコアの総和の最大値という区間 \(dp\) で解くことが出来ます。状態数 \(O(N^2)\) 遷移 \(O(N)\) なので計算量は \(O(N^3)\)です。

部分点2 \((N \le 3000)\)

\(dp[i][j]\) について考えます。この区間における最適解で最初に座らせる人が \(i\) でも \(j\)でもないとします。その人を \(k\) とし、 \(dp[i][k - 1]\) で最初に座らせる人を \(l\) , \(dp[k + 1][j]\) で最初に座らせる人を \(m\) とします。その時、 \(A_l - A_i = x, A_k - A_l = y, A_q - A_k = z, A_j - A_m = w\) として元の最適解での 人 \(k, l, m\) を座らせたときのスコアは \(2 \times (x + y + z + w)\) となるが、 \(l, k, m\) の順に座らせると \(x + 2 \times y + 3 \times z + 3 \times w\) 、\(m, k, l\) の順に座らせると \(3 \times x + 3 \times y + 2 \times z + w\)となり、足すと元の最適解の \(2\) 倍を超えるので、最初に座らせるべきは \(k\) ではないことが示せます。これを \(i, j\) 以外のすべての人について考えることで、 最適解で最初に座る人が \(i\) か \(j\) であることが示せます。よって遷移が \(O(1)\) となりこの問題を解くことができます。

満点

ここで \(A\) に \(0, M + 1\) を加えてソートし、\(B_i = A_{i + 1} - A_i\) として長さ \(N + 1\) の数列 \(B\) を考えると、以下の問題に言い換えられる。

\(N - 1\) 回次の操作を行う。 \(i\) 回目の操作では、 \(B\) の左右の要素どちらかを選び、その要素を \(p\) とし、 \(p \times (N - i)\) をコストとして払い削除する。全体のコストの総和を最小化せよ。

まず、言い換え後の問題で左から取る部分と右から取る部分の境界を固定した問題を考える。左、右の数列をそれぞれ \(x,y\) と置く。そして、更に問題を以下のように言い換える。

\(x,y\) をそれぞれ自体の順番は入れ替えないでマージする。それぞれの要素に対する、その要素 \( \times \)「自分より奥にある自分以外の数列から来ている要素の個数」の総和を最小化せよ。

ただし、同じ数列から来ている要素をコストとしてカウントするとマージ後の数列を \(z\) として \(\sum_{i=1}^{N} (N-i+1) \times z_i\) の最小化になることに注意する。(この \(2\) 個の差分は定数であり簡単に計算できる。) \(x,y\) が両方単調増加ならば自明である。( \(z\) を単調増加にすることが出来、これが明らかな下界だからである。)

さて、\(x_i \ge x_{i+1}\) となる \(i\) があったとする。この 2 個の要素の間に y の要素が入らない最適解の存在を示そう。

\((x_i,x_{i+1},y_1,y_2,...,y_n)\) のコストを \(p\) 、 \((x_i,y_1,y_2,...,y_n,x_{i+1})\) のコストを \(q\)、 \((y_1,y_2,...,y_n,x_i,x_{i+1})\) のコストを \(r\)として、

\(p - q = n \times x_{i+1} - \sum_{i=1}^{N} (y_i)\) , \(q - r = n \times x_i - \sum_{i=1}^{N} (y_i)\)

ここで、 \(q\) が最適解ということは上の式が \(0\) 超過、下の式が \(0\) 未満となるということであるがこれは \(x_i > x_{i+1}\) に矛盾する。よって、\(x_i,x_{i+1}\) は必ず隣り合うという制限を付け加えても答えは変わらない。

更に、 \(c = (x_i + x_{i+1}) / 2\) とすると、 \(x_i,x_{i+1}\) を共に \(c\) に置き換えてしまっても問題ない。

\((c,c,y_1,y_2,...,y_n)\) のコストを \(p`\) 、 \((c,y_1,y_2,...,y_n,c)\) のコストを \(q`\) 、 \((y_1,y_2,...,y_n,c,c)\) のコストを \(r`\) として、

上と下のコストは \(x_i,x_{i+1}\) から \(c,c\) になっても変わらず、かつ \(p` - q` = q` - p`\) であることが確認できる。つまり、このような変更を施しても最適解のコストは変わらない。

ここまでで \(x_i > x_{i+1}\) を満たすならばこれらは最適解において隣り合っていること、更に平均に置き換えてもいいことが証明出来た。これを一般化して \(x_i \ge x_{i+1} \ge ... \ge x_{i+k} \) の場合も示そう。

前者は \(x_{i+j},x_{i+j+1}\) が隣り合っていることより自明である。

後者については、まず \(x_i,x_{i+1},...,x_{i+k}\) が全て隣り合っている場合は全てを \(c\) に置き換えてもコストに影響はない。更に、全てが \(c\) になった場合は \(c, y_1, c\) のようになっている場合自明にどちらかに寄せた方がいいことが示せる。つまりこの操作を行っても最適解のコストは変わらない。

さて、\(x\) に対して「広義単調減少の部分を全て平均値に置き換える」ことを繰り返して \(x\) を広義単調増加にする。これは末尾に 1 要素ずつ追加していき、はじめて \(x_i < (x_{i+1} + x_{i+2} + ... + x_k)/(k - i)\) を満たす最大の \(i\) を二分探索で求めることで常に \(x\) が単調増加であることを保ちつつ要素を追加できる。

そして、\(x,y\) を単調増加にするとセグ木に以下の情報を載せることでこの問題のコストを計算できる。(こんなことをする必要はないが後々 \(x,y\) が動くのでこのようにしておく。)

\(l \le x_i < r\) を満たす \(i\) の個数, \(x_i\) の総和、 \(l \le y_i < r\) を満たす \(i\) の個数, \(y_i\) の総和、 \(l \le x_i < y_j < r\) を満たす \((i,j)\) に対する \(x_i\) の総和、 \(l \le y_j \le x_i < r\) を満たす \((i,j)\) に対する \(y_j\) の総和

ここで元の問題は数列 \(B\) に対して \(x=(B_1,B_2,...,B_i),y=(B_{i+3},B_{i+4},...,B_{N+1})\) とした場合の問題を解くことになる。

\(x\) を RLE して持つことにすると、削除回数が追加回数で抑えられ、追加回数は \(O(N)\) なので \(x_i = a\) を満たす \(i\) を \(k\) 個追加 or 削除するクエリが \(O(N)\) 回来ることになる。\(y\) についても同様である。(\(y\) は逆から見ていることに注意)

よって、セグ木に \(O(N)\) 回クエリを投げることになるためこの問題を \(O(N \log N)\) で解くことが出来た。