Official

F - Replace by Average Editorial by maspy


操作の過程で \(A_i\leq 0\) となることはありません。したがって、操作結果の \(\sum A_i\) としてありうる最小値が存在します。

最小値を与える操作結果の数列をひとつとり、それを \(B\) と書くことにします。また、これらの第 \(x\)\(A_x, B_x\) をこの解説では \(A(x)\), \(B(x)\) と書くことにします。

また便宜上、\(x < 1\) または \(N < x\) に対して \(A(x) = B(x) = \infty\) であると定めておきます。


\(B\) の凸性

\((i,j,k) = (x-1,x,x+1)\) であるような操作によって \(\sum_{x=1}^N B(x)\) が減少しないことから、任意の \(x\) に対して \(2B(x) \leq B(x-1) + B(x+1)\) が成り立ちます。

この性質を満たす関数 \(B\colon \Z\longrightarrow \mathbb{R}\) を、離散凸関数といいます


\(B\) の最小値

\(A\) から \(B\) を得る過程で、項が増加するような操作は行わないとしてよいです。このとき、操作によって数列の最小値が不変であることが確認できます。つまり、\(\min_{x\in \mathbb{Z}} B(x) = \min_{x\in \mathbb{Z}} A(x)\) が分かります。

この考察を一般化して、次を示すことができます:任意の \(p\in \mathbb{Z}\) に対して、\(\min_{x\in \mathbb{Z}} (B(x) - px) = \min_{x\in \mathbb{Z}} (A(x) - px).\)


\(B\) の決定

\(a_p := \min_{x\in \mathbb{Z}} (A(x) - px)\) と書くことにします。

上述の性質

  1. \(B\) は凸つまり、\(2B(x) \leq B(x-1) + B(x+1)\)
  2. \(\min_{x\in \mathbb{Z}} (B(x) -px) = a_p\)

から、一意に \(B\) を決定することが可能です。実際、

\(B(x) = \max_{p\in \mathbb{Z}}(px + a_p)\)

が成り立つことが証明できます。

\(B(x) \geq \max_{p\in \mathbb{Z}}(px + a_p)\) の証明

\(x\) を固定して、任意の \(p\in\mathbb{Z}\) に対して \(B(x)\geq px + a_p\) を示せばよいですが、これは性質 2. より明らかです。

\(B(x) \leq \max_{p\in \mathbb{Z}}(px + a_p)\) の証明

\(x\) を固定して、\(B(x) \leq px+a_p\) となる \(p\) をひとつ挙げればよいです。\(B\) の凸性より \(B(x)-B(x-1)\leq p\leq B(x+1)-B(x)\) となる \(p\in \mathbb{Z}\) が存在し、この \(p\) に対して \(B(x) - px = \min_{y\in \mathbb{Z}}(B(y) - py)\) が成り立ちます。右辺は \(a_p\) に等しいのでしたから、\(B(x) - px = a_p\) となり、\(B(x) \leq px + a_p\) となる \(p\) の存在が確かめられました。


結局本問題の最適解 \(B\) は、次のようにして定まることが分かりました。

  • \(a_p = \min_{x\in \mathbb{Z}}(A(x) - px)\) とおく
  • \(B(x) = \max_{p\in \mathbb{Z}}(px + a_p)\) である。

\(p\) に対して、\(a_p = A(x) - px\) となる \(x\) は、\(A\) の下側凸包上の点のどこかです。下側凸包の点を列挙すれば、各 \(p\) に対して \(a_p = A(x) - px\) となる \(x\) をひとつ見つけることができます。このような \(x\)\(x_p\) と書くことにします。

\(x_p\leq x\leq x_{p+1}\) に対して、\(B(x) = \max(px+a_p, (p+1)x + a_{p+1})\) が成り立ちます。実際

  • \(q \leq p\) ならば \(qx_p+a_q\leq px_p + a_p\) より \(qx_p + a_q\leq px_p+a_p\)
  • \(q \geq p+1\) ならば \(qx_{p+1}+a_q\leq qx_{p+1} + a_{p+1}\) より \(qx + a_q\leq (p+1)x_{p+1}+a_{p+1}\)

となるためです。この式によって \(x_p\leq x\leq x_{p+1}\) となる \(B(x)\) が計算でき、すべての \(B(x)\) を求めることができます。

以上を適切に実装すると、本問題は \(O(N)\) 時間で解くことができます。


以下の図は、\(A = (4, 1, 4, 1, 3, 2, 3, 4, 4)\) に対するものです。

posted:
last update: