[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;
}