Editorial


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

naskya さんのユーザー解説 (時間計算量: )


与えられた数列 の項に を加える操作を繰り返して、なるべく少ない操作回数(これを「最適」ということにします)で等差数列 を作ることを考えます。

このとき、ある が存在して です(操作の前後で不変な項が存在します)。

なぜなら、この問題では数列の項を増やす操作しかできないため ならば ですが、これが任意の について成り立つとすると全ての項への操作回数をそれぞれ だけ少なくした も条件のもとで作れる数列となり、 が最適であることに矛盾するためです。

そこで、 を満たす添字 をとることができます(fixed の f のつもりです)。また最適な等差数列の公差を とすると、操作後の数列 の各項は以下のように表せます。

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

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


は数列の固定する項の添字 で、この問題では より を決める全探索を考えます。

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

を最小化したい

操作によって数列の各項は元の値以上になる 必要があるため、 でなければなりません。

の場合を考え ( なら です)、この不等式の両辺を で割ると を得ます。

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

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

を決めるごとに の上限と下限の計算に 時間が掛かり、その計算を を変えて 回繰り返すため全体の時間計算量は です。

Writer解 (時間計算量:)


簡単な問題


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

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

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

初項を, 公差を, 項目をと置きであるようなについて

  • のとき だけ に1を足す。
    • であるときにに2回だけ1を足すとを等差数列にすることができます。
  • のとき のそれぞれに だけ1を足す。
    • であるときにそれぞれに1回だけ1を足すことでを等差数列にすることができます。

この2つの操作を1回行ったとき、問題文がいうような操作回数はそれぞれだけかかることがわかります。

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

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

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

もとの問題


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

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

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

三分探索


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

定義よりで極小値を持つときで極大値を持ちます。

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

結局の答え


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

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

以上より、答えはです。 このとき三分探索にだけかかり、三分探索内で操作回数を求めるのにだけかかるため、この解法での時間計算量はです。

の値が小さいのでも十分に高速ですが、こちらの解法ではの値がより大きくなっても解くことができます。
ただし、ある公差で定めたときの操作回数の最大値はに比例するような形で増加します。そのため操作回数の計算中にオーバーフローを起こす可能性があることに留意すべき必要があることに注意してください。

実装例(C++)