Editorial
以下に、2つの解説を記載します。
naskyaさんの解説はWriter解よりも時間計算量は悪いですが、Writer解よりも数学的に厳密であるので先に記載します。
Writer解は時間計算量こそ良いですが、数学的に怪しい部分や非自明なところを含むかもしれません。
naskya さんのユーザー解説 (時間計算量: Θ(N2))
与えられた数列 A=(A1,A2,…,AN) の項に 1 を加える操作を繰り返して、なるべく少ない操作回数(これを「最適」ということにします)で等差数列 A′=(A1′,A2′,…,AN′) を作ることを考えます。
このとき、ある i が存在して Ai=Ai′ です(操作の前後で不変な項が存在します)。
なぜなら、この問題では数列の項を増やす操作しかできないため Ai=Ai′ ならば Ai<Ai′ ですが、これが任意の i について成り立つとすると全ての項への操作回数をそれぞれ Δ:=1≤i≤NminAi′−Ai>0 だけ少なくした A′′:=(A1′−Δ,A2′−Δ,…,AN′−Δ) も条件のもとで作れる数列となり、A′ が最適であることに矛盾するためです。
そこで、Af=Af′ を満たす添字 f (1≤f≤N) をとることができます(fixed の f のつもりです)。また最適な等差数列の公差を d とすると、操作後の数列 A′ の各項は以下のように表せます。
数列 A を数列 A′ にするために必要な操作の回数は
i=1∑N(Ai′−Ai)=(i=1∑NAi′)−(i=1∑NAi)=(i=1∑NAf+(i−f)d)−(i=1∑NAi)=N(Af+2N+1−2fd)−i=1∑NAi
です。N と i∑Ai は定数なのでこれは f と d のみに依って決まる量(最小化したいので cost のつもりで C と名付けます)となります。
C(f,d):=N(Af+2N+1−2fd)−i=1∑NAi
f は数列の固定する項の添字 (1,2,…,N) で、この問題では N≤103 より f を決める全探索を考えます。
f を決めると最適な d に関して以下のような目標が立てられます。
C(f,d):=N(Af+2N+1−2fd)−i=1∑NAi を最小化したい →⎩⎨⎧d が小さいほどよいd はなんでもよいd が大きいほどよい(N+1−2f>0)(N+1−2f=0)(N+1−2f<0)⋯⋯①
操作によって数列の各項は元の値以上になる (Ai≤Ai′=Af+(i−f)d) 必要があるため、Ai−Af≤(i−f)d でなければなりません。
i=f の場合を考え (i=f なら Af=Af′ です)、この不等式の両辺を (i−f) で割ると {i−fAi−Af≥di−fAi−Af≤d(i−f<0)(i−f>0) を得ます。
これが全ての i(=f) に対して成り立つ必要があることと、問題の制約より d は正の整数である必要があることから、整理して
max(1,f<i≤Nmax⌈i−fAi−Af⌉)≤d≤1≤i<fmin⌊i−fAi−Af⌋
が d に対する制約となります。よって、f を決め打ちしてこの d の取りうる範囲の上限と下限を求め、範囲が空でないことを確認した上で (N+1−2f) の符号に応じて①の目標に沿って最適な d を求め、C(f,d) の表式に代入することで各 f に対する最適な操作回数が求まります。
f を決めるごとに d の上限と下限の計算に Θ(N) 時間が掛かり、その計算を f を変えて Θ(N) 回繰り返すため全体の時間計算量は Θ(N2) です。
Writer解 (時間計算量:Θ(NlogAi))
簡単な問題
等差数列の性質から初項と公差の情報があればi項目は一意に定まることがわかります。
そこで、公差を決め打ちして等差数列を作り出すことを考えます。
すると、数列Aを問題文に沿って操作するときに、以下の2通りの操作を選んで行えばいいことに気付きます。
初項をA1, 公差をd, i項目をAiと置きi≥1であるようなiについて
- Ai<A1+d(i−1) のとき (A1+d(i−1))−Ai だけ Ai に1を足す。
- A=(1,2,3,2,5)であるときにA4に2回だけ1を足すとAを等差数列にすることができます。
- Ai>A1+d(i−1) のとき A1,A2,...,Ai−1 のそれぞれに Ai−(A1+d(i+1)) だけ1を足す。
- A=(3,4,5,7,8)であるときにA1,A2,A3それぞれに1回だけ1を足すことでAを等差数列にすることができます。
この2つの操作を1回行ったとき、問題文がいうような操作回数はそれぞれ∣(A1+d(i−1))−Ai∣と∣(A1+d(i−1))−Ai∣×(i−1)だけかかることがわかります。
それを踏まえてなにか適当な数列で公差を全探索する実験を行うとわかりますが、操作回数は数列によって
- 広義単調減少した後に極小値を取って広義単調増加に転ずる
- 常に広義単調増加する
という2パターンしかないことに気づきます(例えば{1,3,4,5}のような場合に公差を1に定めるのが最善で、それ以降の公差では操作回数が単調増加します。また、サンプル1などは減少した後に増加します)。
ゆえにこの簡単な問題の答えは操作回数をグラフとしてプロットしたときの極小値、もしくは操作回数0以上での最小値となります。
もとの問題
公差を全探索すればおおよそ問題が解けそうです。しかし、もとの大きな問題で取るべき最適な公差はもしかしたら109などであるかもしれません。そのような場合、線形探索ですら探索するのは不可能です。
そこで、以下のようなことを考えてみます。
f(d)=交差をdとしたときに数列Aを等差数列にするのに必要な操作回数
言うまでもなく、この関数は「単調減少->単調増加」もしくは「ずっと単調増加」の何れかのパターンに該当します。
三分探索
さらに、g(d)を以下のように定義します。
g(d)=K−f(d)
定義よりf(d)がd≥1,d∈Nで極小値を持つときg(d)はdで極大値を持ちます。
最小の操作回数がg(d)の極大値であることは定義より自明であるので、三分探索を行うことでうまくそのようなdを求めることができるような状態まで持ち込めました。
f(x)によってはg(d)が1≤dにおいて極大値を持たないこともありますが、その場合でも1≤dなるdについてg(d)の最大値が最小の操作回数となります。
結局の答え
三分探索を行った結果のg(d)の極大値、もしくは定義域(d≥1)内での最大値が0以上ならできます。
そうでないならできません。
この問題では109がAiの最大値です。log3109≃19ですが、それでは探索が不十分なケースがいくつか存在するので、おおよそ50~80回程度探索を行うかある程度のところまで狭めたらその狭めた区間内をすべて探索するようにすれば必要十分です。
以上より、答えはf(d) (ただしg(d)≥0)です。
このとき三分探索にΘ(logAi)だけかかり、三分探索内で操作回数を求めるのにΘ(N)だけかかるため、この解法での時間計算量はΘ(NlogAi)です。
Nの値が小さいのでΘ(N2)も十分に高速ですが、こちらの解法ではNの値がより大きくなっても解くことができます。
ただし、ある公差dを1≤d≤max(A1,A2,...,AN)で定めたときの操作回数の最大値はNに比例するような形で増加します。そのため操作回数の計算中にオーバーフローを起こす可能性があることに留意すべき必要があることに注意してください。
実装例(C++)