完成した数列はどこかで符号がマイナスからプラスに切り替わることに注目する。$N=5$なら、
- $+++++$
- $-++++$
- $--+++$
- $---++$
- $----+$
- $-----$
の6通りがありえる。たとえば$A_3$で符号が切り替わると決めてしまうと、あとは$A_3, A_4, A_5$の好きな数に好きなだけ4を掛けて単調非減少にして、$A_2, A_1$にも4を掛けて単調非減少にして、最後に$A_2, A_1$に$-2$を掛ければ全体として単調非減少になっている。
そこで、$f^+(x) := A_x, A_{x+1}, ..., A_{N}$を単調非減少にするための最小コスト、と定める。おそらく$f^+(N+1) = f^+(N) = 0$からスタートして$x=N-1, N-2, ..$と順に$f^+(x)$の値を求めていけそう。さらに、$f^-(x) := A_{x}, A_{x-1},..., A_{1}$を単調非減少ににするための最小コスト、とすれば$(f^-(x) + x) + f^+(x+1)$の最小値が答えになる。（$+x$は$-2$を掛けるぶんのコスト。）
さて、$f^+$を求める具体的な方法が問題になる。この手順が与えられれば、$f^-$は同じ方法を逆順の配列に適用するだけでよい。先に述べた通り、$f^+(N+1)=0$からスタートして降りていくことにする。とりあえず、正しくないがシンプルな方針から:
- $A_x \le A_{x+1}$なら$f(x) := f(x+1)$。
- $A_x > A_{x+1}$なら$A_{x+1}$に何回か$4$を掛けて非減少になるようにする。つまり、$A_x \le 4^k A_{x+1}$となるような最小の$k$を求めて、以降の$A_{x+2}, ..., A_{N}$にも同じだけ$4$を掛ける。このとき、$f(x) := f(x+1) + 2k(N-x)$となる。
この方法の問題点は入力例1に適用してみればわかる:
4
3 1 4 1
$f(5) = 0, f(4) = 0, f(3) = 2, f(2) = 2$までは正しく求まるが、$A_1=3$を処理する際に$4$を掛ける必要があるのは$A_2=1$だけで、$A_3, A_4$はそのままでいいことを見落としていた。つまり、$A_2, A_3$の間にはすでに$4$倍の差があるので、一回分の$4$掛けに限っては$A_2$で吸収されてしまうことになる。一般に、$A_{x+1}$が$A_x$の$4^k$倍以上である時、$k$回ぶんの$4$掛けは$A_x$に吸収されて$A_{x+1}$以降には影響しない。この$k$を$x$の 容量 と呼ぶことにする。上の手順で降りていくとき、各$A_x$について（容量が正なら）$(x, 容量)$のペアをスタックに積んでいくことにする。
- $A_x \le A_{x+1}$なら$f(x) := f(x+1)$。$x$の容量が正ならスタックに$(x, 容量)$を積む。
- $A_x > A_{x+1}$なら$A_{x+1}$に何回か$4$を掛けて非減少になるようにする。つまり、$A_x \le 4^k A_{x+1}$となるような最小の$k$を求める。スタックの先頭が$(y, 容量)$になっているとき、$A_{x+1}, ..., A_{y}$に$\min (容量, k)$だけ$4$を掛ける。このとき、操作回数は$2\min(k, 容量)(y-x)$だけ増えるが、容量が$k$より小さい場合はさらにスタックをポップしながら$k$回の$4$掛けが終わるまで繰り返す。
各インデックスについて、スタックへのpushとpopは1回しか行われないので、スタック操作は全体で${O}(N)$になっている。
