2020年1月1日水曜日

CADDi 2018 E - Negative Doubling

完成した数列はどこかで符号がマイナスからプラスに切り替わることに注目する。N=5N=5なら、

  • ++++++++++
  • −++++-++++
  • −−+++--+++
  • −−−++---++
  • −−−−+----+
  • −−−−−-----

の6通りがありえる。たとえばA3A_3で符号が切り替わると決めてしまうと、あとはA3,A4,A5A_3, A_4, A_5の好きな数に好きなだけ4を掛けて単調非減少にして、A2,A1A_2, A_1にも4を掛けて単調非減少にして、最後にA2,A1A_2, A_1に−2-2を掛ければ全体として単調非減少になっている。

そこで、f+(x):=Ax,Ax+1,...,ANf^+(x) := A_x, A_{x+1}, ..., A_{N}を単調非減少にするための最小コスト、と定める。おそらくf+(N+1)=f+(N)=0f^+(N+1) = f^+(N) = 0からスタートしてx=N−1,N−2,..x=N-1, N-2, ..と順にf+(x)f^+(x)の値を求めていけそう。さらに、f−(x):=Ax,Ax−1,...,A1f^-(x) := A_{x}, A_{x-1},..., A_{1}を単調非減少ににするための最小コスト、とすれば(f−(x)+x)+f+(x+1)(f^-(x) + x) + f^+(x+1)の最小値が答えになる。（+x+xは−2-2を掛けるぶんのコスト。）

さて、f+f^+を求める具体的な方法が問題になる。この手順が与えられれば、f−f^-は同じ方法を逆順の配列に適用するだけでよい。先に述べた通り、f+(N+1)=0f^+(N+1)=0からスタートして降りていくことにする。とりあえず、正しくないがシンプルな方針から:

  1. Ax≤Ax+1A_x \le A_{x+1}ならf(x):=f(x+1)f(x) := f(x+1)。
  2. Ax>Ax+1A_x > A_{x+1}ならAx+1A_{x+1}に何回か44を掛けて非減少になるようにする。つまり、Ax≤4kAx+1A_x \le 4^k A_{x+1}となるような最小のkkを求めて、以降のAx+2,...,ANA_{x+2}, ..., A_{N}にも同じだけ44を掛ける。このとき、f(x):=f(x+1)+2k(N−x)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)=2f(5) = 0, f(4) = 0, f(3) = 2, f(2) = 2までは正しく求まるが、A1=3A_1=3を処理する際に44を掛ける必要があるのはA2=1A_2=1だけで、A3,A4A_3, A_4はそのままでいいことを見落としていた。つまり、A2,A3A_2, A_3の間にはすでに44倍の差があるので、一回分の44掛けに限ってはA2A_2で吸収されてしまうことになる。一般に、Ax+1A_{x+1}がAxA_xの4k4^k倍以上である時、kk回ぶんの44掛けはAxA_xに吸収されてAx+1A_{x+1}以降には影響しない。このkkをxxの 容量 と呼ぶことにする。上の手順で降りていくとき、各AxA_xについて（容量が正なら）(x,容量)(x, 容量)のペアをスタックに積んでいくことにする。

  1. Ax≤Ax+1A_x \le A_{x+1}ならf(x):=f(x+1)f(x) := f(x+1)。xxの容量が正ならスタックに(x,容量)(x, 容量)を積む。
  2. Ax>Ax+1A_x > A_{x+1}ならAx+1A_{x+1}に何回か44を掛けて非減少になるようにする。つまり、Ax≤4kAx+1A_x \le 4^k A_{x+1}となるような最小のkkを求める。スタックの先頭が(y,容量)(y, 容量)になっているとき、Ax+1,...,AyA_{x+1}, ..., A_{y}にmin⁡(容量,k)\min (容量, k)だけ44を掛ける。このとき、操作回数は2min⁡(k,容量)(y−x)2\min(k, 容量)(y-x)だけ増えるが、容量がkkより小さい場合はさらにスタックをポップしながらkk回の44掛けが終わるまで繰り返す。

各インデックスについて、スタックへのpushとpopは1回しか行われないので、スタック操作は全体でO(N){O}(N)になっている。

投稿者