Editorial

以下に、2つの解説を記載します。
naskyaさんの解説はWriter解よりも時間計算量は悪いですが、Writer解よりも数学的に厳密であるので先に記載します。
Writer解は時間計算量こそ良いですが、数学的に怪しい部分や非自明なところを含むかもしれません。

naskya さんのユーザー解説 (時間計算量: Θ(N2)\Theta\left(N^2\right))

与えられた数列 A=(A1,A2,,AN)A = (A_1, A_2, \dots, A_N) の項に 11 を加える操作を繰り返して、なるべく少ない操作回数(これを「最適」ということにします)で等差数列 A=(A1,A2,,AN)A' = (A'_1, A'_2, \dots, A'_N) を作ることを考えます。

このとき、ある ii が存在して Ai=AiA_i = A'_i です(操作の前後で不変な項が存在します)。

なぜなら、この問題では数列の項を増やす操作しかできないため AiAiA_i \neq A'_i ならば Ai<AiA_i < A'_i ですが、これが任意の ii について成り立つとすると全ての項への操作回数をそれぞれ Δmin1iNAiAi>0\Delta \coloneqq \displaystyle\min_{1 \leq i \leq N} A'_i - A_i > 0 だけ少なくした A(A1Δ,A2Δ,,ANΔ)A'' \coloneqq (A'_1 - \Delta, A'_2 - \Delta, \dots, A'_N - \Delta) も条件のもとで作れる数列となり、AA' が最適であることに矛盾するためです。

そこで、Af=AfA_f = A'_f を満たす添字 f (1fN)f \ (1 \leq f \leq N) をとることができます(fixed の f のつもりです)。また最適な等差数列の公差を dd とすると、操作後の数列 AA' の各項は以下のように表せます。

数列 AA を数列 AA' にするために必要な操作の回数は

i=1N(AiAi)=(i=1NAi)(i=1NAi)=(i=1NAf+(if)d)(i=1NAi)=N(Af+N+12f2d)i=1NAi\begin{array}{ll} & \hspace{1em} \displaystyle\sum_{i=1}^N \left( A'_i - A_i \right) \\ &= \left(\displaystyle\sum_{i=1}^N A'_i \right) - \left(\displaystyle\sum_{i=1}^N A_i \right) \\ &= \left(\displaystyle\sum_{i=1}^N A_f + (i-f) d \right) - \left(\displaystyle\sum_{i=1}^N A_i \right) \\ &= N \left(A_f + \frac{N+1-2f}{2} \, d \right) - \displaystyle\sum_{i=1}^N A_i\end{array}

です。NNiAi\displaystyle\sum_i A_i は定数なのでこれは ffdd のみに依って決まる量(最小化したいので cost のつもりで C と名付けます)となります。

C(f,d)N(Af+N+12f2d)i=1NAiC(\textcolor{red}{f}, \textcolor{blue}{d}) \coloneqq N \left(A_{\textcolor{red}{f}} + \frac{N+1-2\textcolor{red}{f}}{2} \, \textcolor{blue}{d} \right) - \displaystyle\sum_{i=1}^N A_i


ff は数列の固定する項の添字 (1,2,,N)(1, 2, \dots, N) で、この問題では N103N \leq 10^3 より ff を決める全探索を考えます。

ff を決めると最適な dd に関して以下のような目標が立てられます。

C(f,d)N(Af+N+12f2d)i=1NAiC(f, \textcolor{blue}{d}) \coloneqq N \left(A_f + \frac{N+1-2f}{2} \, \textcolor{blue}{d} \right) - \displaystyle\sum_{i=1}^N A_i を最小化したい {d が小さいほどよい(N+12f>0)d はなんでもよい(N+12f=0)d が大きいほどよい(N+12f<0)\to \begin{cases} \textcolor{blue}{d}\ \footnotesize{が小さいほどよい} & (N+1-2f > 0)\\ \textcolor{blue}{d}\ \footnotesize{はなんでもよい} & (N+1-2f = 0) \\ \textcolor{blue}{d}\ \footnotesize{が大きいほどよい} & (N+1-2f < 0) \end{cases} \hspace{0.75em} \cdots\cdots ①

操作によって数列の各項は元の値以上になる (AiAi=Af+(if)d)(A_i \leq A'_i = A_f + (i-f) d) 必要があるため、AiAf(if)dA_i - A_f \leq (i-f)d でなければなりません。

ifi \neq f の場合を考え (i=fi = f なら Af=AfA_f = A'_f です)、この不等式の両辺を (if)(i-f) で割ると {AiAfifd(if<0)AiAfifd(if>0)\begin{cases} \frac{A_i - A_f}{i-f} \geq d & (i-f < 0) \\ \frac{A_i - A_f}{i-f} \leq d & (i-f > 0) \end{cases} を得ます。

これが全ての i(f)i (\neq f) に対して成り立つ必要があることと、問題の制約より dd は正の整数である必要があることから、整理して

max(1,maxf<iNAiAfif)dmin1i<fAiAfif\max \left( 1, \displaystyle\max_{f < i \leq N} \left\lceil \frac{A_i - A_f}{i-f} \right\rceil \right) \leq d \leq \displaystyle\min_{1 \leq i < f} \left\lfloor \frac{A_i - A_f}{i-f} \right\rfloor

dd に対する制約となります。よって、ff を決め打ちしてこの dd の取りうる範囲の上限と下限を求め、範囲が空でないことを確認した上で (N+12f)(N + 1 - 2f) の符号に応じて①の目標に沿って最適な dd を求め、C(f,d)C(f, d) の表式に代入することで各 ff に対する最適な操作回数が求まります。

ff を決めるごとに dd の上限と下限の計算に Θ(N)\Theta(N) 時間が掛かり、その計算を ff を変えて Θ(N)\Theta(N) 回繰り返すため全体の時間計算量は Θ(N2)\Theta\left(N^2\right) です。

Writer解 (時間計算量:Θ(NlogAi)\Theta(N \log{A_i}))

簡単な問題

NN項の数列AAがある。AAは等差数列かもしれないしそうではないかもしれない
AAの各要素に1だけ値を足す操作を0回以上何度でも行えるとき、AAを公差が0より大きな等差数列にするまでに必要な最小の操作回数を求めよ

  • 2N1032 \le N \le 10^3
  • 1Ai1041 \le A_i \le 10^{4}

等差数列の性質から初項と公差の情報があればii項目は一意に定まることがわかります。

そこで、公差を決め打ちして等差数列を作り出すことを考えます。
すると、数列AAを問題文に沿って操作するときに、以下の2通りの操作を選んで行えばいいことに気付きます。

初項をA1A_1, 公差をdd, ii項目をAiA_iと置きi1i \ge 1であるようなiiについて

  • Ai<A1+d(i1)A_i < A_1+d(i-1) のとき (A1+d(i1))Ai\left(A_1+d(i-1)\right) - A_i だけ AiA_i に1を足す。
    • A=(1,2,3,2,5)A = (1, 2, 3, 2, 5)であるときにA4A_4に2回だけ1を足すとAAを等差数列にすることができます。
  • Ai>A1+d(i1)A_i > A_1+d(i-1) のとき A1,A2,...,Ai1A_1, A_2, ... , A_{i-1} のそれぞれに Ai(A1+d(i+1)) A_i - \left(A_1+d(i+1)\right) だけ1を足す。
    • A=(3,4,5,7,8)A = (3, 4, 5, 7, 8)であるときにA1,A2,A3A_1, A_2, A_3それぞれに1回だけ1を足すことでAAを等差数列にすることができます。

この2つの操作を1回行ったとき、問題文がいうような操作回数はそれぞれ(A1+d(i1))Ai|\left(A_1+d(i-1)\right) - A_i|(A1+d(i1))Ai×(i1)|\left(A_1+d(i-1)\right) - A_i|\times (i-1)だけかかることがわかります。

それを踏まえてなにか適当な数列で公差を全探索する実験を行うとわかりますが、操作回数は数列によって

  • 広義単調減少した後に極小値を取って広義単調増加に転ずる
  • 常に広義単調増加する

という2パターンしかないことに気づきます(例えば{1,3,4,5}\lbrace 1, 3, 4, 5 \rbraceのような場合に公差を1に定めるのが最善で、それ以降の公差では操作回数が単調増加します。また、サンプル1などは減少した後に増加します)。 ゆえにこの簡単な問題の答えは操作回数をグラフとしてプロットしたときの極小値、もしくは操作回数0以上での最小値となります。

もとの問題

公差を全探索すればおおよそ問題が解けそうです。しかし、もとの大きな問題で取るべき最適な公差はもしかしたら10910^9などであるかもしれません。そのような場合、線形探索ですら探索するのは不可能です。

そこで、以下のようなことを考えてみます。

f(d)=交差をdとしたときに数列Aを等差数列にするのに必要な操作回数f(d) = 交差をdとしたときに数列Aを等差数列にするのに必要な操作回数

言うまでもなく、この関数は「単調減少->単調増加」もしくは「ずっと単調増加」の何れかのパターンに該当します。

三分探索

さらに、g(d)g(d)を以下のように定義します。

g(d)=Kf(d)g(d) = K-f(d)

定義よりf(d)f(d)d1,dNd \ge 1, d \in \Nで極小値を持つときg(d)g(d)ddで極大値を持ちます。

最小の操作回数がg(d)g(d)の極大値であることは定義より自明であるので、三分探索を行うことでうまくそのようなddを求めることができるような状態まで持ち込めました。
f(x)f(x)によってはg(d)g(d)1d1 \le dにおいて極大値を持たないこともありますが、その場合でも1d1 \le dなるddについてg(d)g(d)の最大値が最小の操作回数となります。

結局の答え

三分探索を行った結果のg(d)g(d)の極大値、もしくは定義域(d1d \ge 1)内での最大値が0以上ならできます。 そうでないならできません。

この問題では10910^9AiA_iの最大値です。log310919\log_3{10^9} \simeq 19ですが、それでは探索が不十分なケースがいくつか存在するので、おおよそ50~80回程度探索を行うかある程度のところまで狭めたらその狭めた区間内をすべて探索するようにすれば必要十分です。

以上より、答えはf(d) (ただしg(d)0)f(d) \ (ただしg(d) \ge 0)です。 このとき三分探索にΘ(logAi)\Theta(\log A_i)だけかかり、三分探索内で操作回数を求めるのにΘ(N)\Theta(N)だけかかるため、この解法での時間計算量はΘ(NlogAi)\Theta(N\log A_i)です。

NNの値が小さいのでΘ(N2)\Theta(N^2)も十分に高速ですが、こちらの解法ではNNの値がより大きくなっても解くことができます。
ただし、ある公差d\hspace{0.25em}d\hspace{0.25em}1dmax(A1,A2,...,AN)\hspace{0.1em}1 \le d \le \max(A_1, \hspace{0.1em} A_2, \hspace{0.1em}..., \hspace{0.1em}A_N)で定めたときの操作回数の最大値はNNに比例するような形で増加します。そのため操作回数の計算中にオーバーフローを起こす可能性があることに留意すべき必要があることに注意してください。

実装例(C++)