最適解の構造を観察することで、\(O(N)\) 時間で解きます。

最適解（「最大値」をとるような \(x\) ）の存在の証明は省略します。

（空でないコンパクト集合上の連続関数は最大値を持つことを用いてもよいですし、以下の議論よりを丁寧に行うことでも証明できます）

観察 1：平均化(1)

\(A_i \geq A_{i+1}\) であるとします。 このとき、\(x_i < x_{i+1}\) であれば、\((x_i, x_{i+1})\) をともに \(\frac{x_i+x_{i+1}}{2}\) に取り換えることで、条件を満たしスコアを減少させないまま、\(x_i = x_{i+1}\) が成り立つようにできます。したがって最適解のうちで \(A_i \geq A_{i+1} \implies x_i =x_{i+1}\) を満たすものの存在が分かります。

観察 2：平均化(2)

この考察をさらに推し進めましょう。 区間 \(I = [l, m)\) および \(J = [m,r)\) に対して \(x\) が定数であることが分かっている。つまり、ある \(x_I, x_J\) に対して

• \(l\leq i < m \implies x_i = x_I\)
• \(m\leq j < r \implies x_j = x_J\)

が成り立つと仮定します。\(i\in I\) に対する \(A_i\) の平均 \(\frac{A_l + \cdots + A_{m-1}}{m-l}\) を \(\text{avg}_I\) と書きます。同様に \(\text{avg}_J\) も定めます。このとき、次が分かります：

• \(\text{avg}_I > \text{avg}_J\) かつ \(x_I < x_J\) であるとき、\(l\leq i < r\) に対して \(x_i\) を一斉に \(a = \frac{(m-l)x_I + (r-m)x_J}{r-l}\) に変化させると、条件を満たしスコアは減少しないまま、\(I\cup J\) 上で \(x_i\) を定数にできる。

なお \(I, J\) の要素数が \(1\) であるときには、この結論は観察 1 と一致しています。

---

観察 1, 2 によって、「定数であることを仮定できる区間」を次々とマージしていきます。より具体的には、区間内での \(A_i\) の平均が降順に並んでいるような隣接区間をマージ可能です。マージを最大限行った結果として、結局次のような \([0, N)\) の分割が得られます。

• \([0, N)\) が区間 \(I_1, \ldots, I_K\) にこの順に分割されており、各区間における \(A_i\) の平均値は単調増加である（\(\text{avg}_{I_1} < \cdots < \text{avg}_{I_K}\) ）。
• 最適解であって、各 \(I_k\) 上では \(x_i\) は定数であるようなものが存在する。

観察 3：偏らせる

上のように区間 \(I_k\) や最適解 \(x_i\) をとります。 \(I_k\) のうち、\(x_i \notin \{0,M\}\) となる区間は高々ひとつであることを示しましょう。

\(I_k\) 上 \(0 < x_i\) となるような最小の \(k\) を \(k_1\) とします。 \(I_k\) 上 \(x_i < M\) となるような最大の \(k\) を \(k_2\) とします。

\(k_1 < k_2\) であるとして矛盾を導きます。

正実数 \(\varepsilon\) に対して、

• \(I_{k_1}\) 上では \(x_i\) に \(-\varepsilon / |I_{k_1}|\) を加える
• \(I_{k_2}\) 上では \(x_i\) に \(+\varepsilon / |I_{k_2}|\) を加える

という操作を考えます。\(\varepsilon\) を十分小さくとることで、\(0\leq x_i \leq M\) が成り立つようにできます。このとき操作は数列に対する条件を保ったまま \(x\) のスコアを増加させるため、\(x\) の最適性に矛盾します。

解法まとめ

まず、「観察2」のような区間の分割 \(I_1, \ldots, I_K\) を計算します。これは、stack を用いるなどして、\(O(N)\) 時間で計算できます。

これらの区間ごとに \(x_i\) は定数で、さらに観察3 より、\(0, M\) 以外の値をとるような区間はこのうち \(1\) つ以下です。\(0, M\) 以外の値をとるような区間 \(I_k\) を決め打って、条件を満たす数列 \(x\) の判定やスコアの計算を行うことで、全体として \(O(N)\) 時間で答を計算することができます。

解答例

https://atcoder.jp/contests/arc128/submissions/26601410