[CADDi 2018]E - Negative Doubling

[Q] https://atcoder.jp/contests/caddi2018/tasks/caddi2018_c
[解説] https://img.atcoder.jp/caddi2018/editorial.pdf

1. Aの値を、log2(A)にしちゃう。

2. 解説に従うと、行う操作は次の2種類とわかる。
(a) Aを−2倍して符号反転。これは1回しか行えない。
(b) Aを4倍。この操作は 2 回の操作として数える。
3 > 2 > 1 < 2 < 3
みたいな列が作れたら、
-6 < -4 < 1 < 2 < 3
~~~~~
単調減少している箇所に-2をかければ、単調増加にできることがわかる。
なので、0 ~ N-1のindex地点を開始地点として、
3. index以降を単調増加列にするために必要な操作回数
4. index以前を単調減少列にするために必要な操作回数
をしれればいいと思う。

3. ある地点からみて、単調増加にするために必要な回数を調べる。
index 0 ~ N-1 について、
N-1からN-1を単調増加にする回数: L[N-1] = 0
N-2からN-1を単調増加にする回数; L[N-2]
...
0 からN-1 を単調増加にする回数: L[0]
を調べたい。
これは、減少列A[0] > A[1] なら、A[1]を4倍し続ければいい。
log2にしたので、log_2(4) = 2.0を足し続ければいい。

4. 単調減少列を調べるには？
Aを反転させれば、3.と同じ処理がまるまる使える。

Q. 例3
N=7
A:29.3 27.0 27.4 28.3 28.8 29.8 29.6 28.3 

1. A は log2 にしておく。
3. 単調増加列にするための操作数を求める。 

6) L[6] = 0
5) 29.6 28.3 は 減少列になっているので、
-> 29.6 30.3
        ~~~~ +2すればいい。
L[4] = 2 // 操作回数が2回
A:29.3 27.0 27.4 28.3 28.8 29.8 29.6 30.3 
                                     ~~~~

4) 29.8 29.6 30.3 
        ~~~~ ~~~~ それぞれ+2.0して
-> 29.8 31.6 32.3 
L[5] = 6 // 2+4
A:29.3 27.0 27.4 28.3 28.8 29.8 31.6 32.3 
                                ~~~~ ~~~~
...

L:34 6 6 6 6 6 2 0 

4. 単調減少列にする操作回数を求める。
Aを反転させ、3.と同様のことをすればいい。
出来上がったRを反転させるとこうなる。

R:0 0 2 8 16 26 26 26 

5. 回答は、L[i] + R[i] + iの最小。
L:34  6  6  6  6  6  2  0 
R: 0  0  2  8 16 26 26 26 

R[i] について。-2倍して反転させるので、要素数 i を加算。
ans = 6+0+1 = 7 が最小。 // index 1 を採用。

Q. 毎回末端まで増加列の確認をしたら、O(N^2)?
A. 高速化したい。
単調具合が密接な範囲を見つけることにした。

1. A[] = 10 1 2 3 4 5
これは、
A[] = 10 1 2 3 4 5
         ~~~~~~~~~ ここを全部、16倍すればベストな増加列になる。ここが密接な範囲。

2. いやらしい例。
A[] = 1000 1 2 101 102
           ~~~ここは1024倍
A[] = 1000 1024 2048 101 102
                     ~~~~~~~ ここは64倍
増加列の中で倍率が違ってしまう。列のおしりまで、個別に加算しないといけない。


さて。
できあがった列を見ると、すべて同じ倍率で変更するしかない範囲になっている。
A[] = 1000 1024 2048 6464 6528
      ~~~~~~~~~~~~~~~~~~~~~~~~ もう一心同体。ひとつながり。密接。

もし先頭に 10000 がきたら、
A[] = 10000 1000 1024 2048 6464 6528
            ~~~~~~~~~~~~~~~~~~~~~~~~ ここを16倍

一定倍率で変更できる密接な範囲を押さえておけば、加算処理をスキップできる。

実装

ll N;

vector<ll> init(vector<ld> &A) {
 ll smooth = N - 2;  // 均等にならせているindex
 ld a[N];
 rep(i, N) a[i] = A[i];
 vector<ll> L(N, 0);

 for (ll i = N - 2; i >= 0; --i) {
   chmax(L[i], L[i + 1]);
   for (ll j = i; j < N - 1; ++j) {
     if (a[j] <= a[j + 1]) break;
     ld dif = a[j] - a[j + 1];
     ll add = 0;
     if (dif > 0) {
       dif += 1.9999999999999;
       add = dif / 2.0;
     }
     a[j + 1] += 2.0 * add;
     L[i] += 2 * add;
     if (j == smooth) { // 密接な範囲の更新
       smooth = i;
       L[i] += 2 * add * (N - j - 2);
       break;
     }
   }
 }
 return L;
}

int main() {
 cincout();

 cin >> N;
 vector<ld> A(N);
 rep(i, N) {
   ll a;
   cin >> a;
   A[i] = log2l(a);
 }

 vector<ll> L = init(A);
 reverse(all(A));
 vector<ll> R = init(A);
 reverse(all(R));

 ll ans = oo;
 rep(i, N) { chmin(ans, L[i] + R[i] + i); }
 cout << ans << endl;
}

https://atcoder.jp/contests/caddi2018/submissions/28796764