AtCoder Caddi 2018 E. Negative Doubling (Stack)

日付: 12月 23, 2018

[E - Negative Doubling](https://atcoder.jp/contests/caddi2018/tasks/caddi2018_c)
## Problem
Given an array of <math><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math>n positive numbers, you can choose a number and multiply it by -2. Calculate the minimum possible number of operations to make the array non-decreasing.

**Constraints:** <math><semantics><mrow><mn>1</mn><mo>≤</mo><mi>n</mi><mo>≤</mo><mn>2</mn><mo>⋅</mo><mn>1</mn><msup><mn>0</mn><mn>5</mn></msup><mo separator="true">,</mo><mtext> </mtext><mn>1</mn><mo>≤</mo><msub><mi>A</mi><mi>i</mi></msub><mo>≤</mo><mn>1</mn><msup><mn>0</mn><mn>9</mn></msup></mrow><annotation encoding="application/x-tex">1\le n \le 2\cdot 10^5,\ 1 \le A_i \le 10^9</annotation></semantics></math>1≤n≤2⋅105, 1≤Ai≤109

## Solution
If we perform the optimal strategy, at least one of the numbers does not change, and all numbers after it is positive, all numbers before it is negative. We define two arrays <math><semantics><mrow><mi>L</mi></mrow><annotation encoding="application/x-tex">L</annotation></semantics></math>L and <math><semantics><mrow><mi>R</mi></mrow><annotation encoding="application/x-tex">R</annotation></semantics></math>R. <math><semantics><mrow><msub><mi>L</mi><mi>i</mi></msub></mrow><annotation encoding="application/x-tex">L_i</annotation></semantics></math>Li is the minimum number of operations needed to make numbers before <math><semantics><mrow><msub><mi>A</mi><mi>i</mi></msub></mrow><annotation encoding="application/x-tex">A_i</annotation></semantics></math>Ai (inclusively) **non-increasing**. <math><semantics><mrow><msub><mi>R</mi><mi>i</mi></msub></mrow><annotation encoding="application/x-tex">R_i</annotation></semantics></math>Ri is the minimum number of operations needed to make numbers after <math><semantics><mrow><msub><mi>A</mi><mrow><mi>n</mi><mo>+</mo><mn>1</mn><mo>−</mo><mi>i</mi></mrow></msub></mrow><annotation encoding="application/x-tex">A_{n+1-i}</annotation></semantics></math>An+1−i (inclusively) **non-decreasing**. We can calculate <math><semantics><mrow><mi>L</mi></mrow><annotation encoding="application/x-tex">L</annotation></semantics></math>L and then reverse <math><semantics><mrow><mi>A</mi></mrow><annotation encoding="application/x-tex">A</annotation></semantics></math>A and calculate <math><semantics><mrow><mi>R</mi></mrow><annotation encoding="application/x-tex">R</annotation></semantics></math>R. If <math><semantics><mrow><mi>L</mi></mrow><annotation encoding="application/x-tex">L</annotation></semantics></math>L and <math><semantics><mrow><mi>R</mi></mrow><annotation encoding="application/x-tex">R</annotation></semantics></math>R is calculated, answer is <math><semantics><mrow><mi>m</mi><mi>i</mi><mi>n</mi><mo>{</mo><msub><mi>L</mi><mrow><mi>i</mi><mo>−</mo><mn>1</mn></mrow></msub><mo>+</mo><mi>i</mi><mo>−</mo><mn>1</mn><mo>+</mo><msub><mi>R</mi><mrow><mi>n</mi><mo>+</mo><mn>1</mn><mo>−</mo><mi>i</mi></mrow></msub><mo>}</mo></mrow><annotation encoding="application/x-tex">min\{L_{i-1} + i-1 + R_{n+1-i}\}</annotation></semantics></math>min{Li−1+i−1+Rn+1−i}.

To calculate <math><semantics><mrow><mi>L</mi></mrow><annotation encoding="application/x-tex">L</annotation></semantics></math>L, iterating <math><semantics><mrow><mi>i</mi></mrow><annotation encoding="application/x-tex">i</annotation></semantics></math>i, if <math><semantics><mrow><msub><mi>A</mi><mi>i</mi></msub><mo>&gt;</mo><msub><mi>A</mi><mrow><mi>i</mi><mo>−</mo><mn>1</mn></mrow></msub></mrow><annotation encoding="application/x-tex">A_i &gt; A_{i-1}</annotation></semantics></math>Ai>Ai−1, we must multiply <math><semantics><mrow><msub><mi>A</mi><mrow><mi>x</mi><mo>⋯</mo><mi>i</mi><mo>−</mo><mn>1</mn></mrow></msub></mrow><annotation encoding="application/x-tex">A_{x\cdots i-1}</annotation></semantics></math>Ax⋯i−1 by 4 until <math><semantics><mrow><msub><mi>A</mi><mrow><mi>i</mi><mo>−</mo><mn>1</mn></mrow></msub><mo>≥</mo><msub><mi>A</mi><mi>i</mi></msub></mrow><annotation encoding="application/x-tex">A_{i-1} \ge A_i</annotation></semantics></math>Ai−1≥Ai. But <math><semantics><mrow><mi>x</mi></mrow><annotation encoding="application/x-tex">x</annotation></semantics></math>x is not known, we can maintain a stack such that its top is always <math><semantics><mrow><mi>x</mi><mo>−</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">x-1</annotation></semantics></math>x−1. If <math><semantics><mrow><msub><mi>A</mi><mrow><mi>i</mi><mo>−</mo><mn>1</mn></mrow></msub><mo>≥</mo><mn>4</mn><msub><mi>A</mi><mi>i</mi></msub></mrow><annotation encoding="application/x-tex">A_{i-1} \ge 4A_i</annotation></semantics></math>Ai−1≥4Ai, <math><semantics><mrow><mi>i</mi><mo>−</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">i-1</annotation></semantics></math>i−1 will not be used. So if <math><semantics><mrow><mi>A</mi><mrow><mi>i</mi><mo>−</mo><mn>1</mn></mrow><mo>≥</mo><mn>4</mn><msub><mi>A</mi><mi>i</mi></msub></mrow><annotation encoding="application/x-tex">A{i-1} \ge 4A_i</annotation></semantics></math>Ai−1≥4Ai, we can calculate after how many operations of multiplying <math><semantics><mrow><msub><mi>A</mi><mi>i</mi></msub></mrow><annotation encoding="application/x-tex">A_i</annotation></semantics></math>Ai by 4, this condition is hold, and push <math><semantics><mrow><mi>i</mi><mo>−</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">i-1</annotation></semantics></math>i−1 into the stack for that number of times.

## Code
```c++
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FI(i,a,b) for(int i=(a);i<=(b);++i)

const int N = 2e5 + 5;
int n, A[N], S[N * 3];
LL L[N], R[N];

void calc(LL *F) {
 for (*S = 0; *S < n;) S[++*S] = 0;
 LL sum = 0;
 FI(i, 2, n) {
 LL x = A[i - 1], y = A[i];
 while (x < y) sum += i - 1 - S[(*S)--], x *= 4;
 while (x >= y * 4) S[++(*S)] = i - 1, y *= 4;
 F[i] = sum * 2;
 }
}

int main() {
    scanf("%d", &n);
    FI(i, 1, n) scanf("%d", A + i);
    calc(L), reverse(A + 1, A + 1 + n), calc(R);
    LL ans = LLONG_MAX;
    FI(i, 1, n) ans = min(ans, L[i - 1] + i - 1 + R[n - i + 1]);
    printf("%lld\n", ans);
}
```

KONGROOの基地

このブログを検索

AtCoder Caddi 2018 E. Negative Doubling (Stack)

コメント

コメントを投稿