問題概要

N個の正の整数値からなる数列$ A_1, A_2, \cdots, A_N$について，1つの要素を-2倍する操作を繰り返す．このとき，数列が非減少列となる最も少ない操作回数を求める．

$ 1 \le N \le 2\times 10^5 $, $ 1 \le A_i \le 10^9 $

解法概要

-2倍する操作を

(a) -2倍する

(b) 4倍する (操作2回分適用)

の2つの操作に分けて考える

(a)を適用する/しない部分 (負の部分/正の部分呼ぶことにする) についてそれぞれ解くことができる．

負の部分と正の部分の境界を全部試す場合，境界を固定したときの時間計算量が$ O(1) $だとしても全体で$ O(N) $となるので，

境界を固定したときの時間計算量が$ O(\log N) $かそれより軽い
負の部分と正の部分それぞれについて $ O(N) $かそれより軽い時間計算量で事前計算ができる

のどちらかであってほしいなあという気持ちになる．

前者もコンテスト中に考えてみたけど厳しそうなので後者で考えてみる．

以下，正の部分に対する (b) の適用について考える．

(b) について考える時の方針として，いちいち配列の値を4倍しているとオーバーフローの恐れがあるので操作回数を持っておく方針で行くべき．

あと，前から順番に考えたくなるけど正の部分は数列$ A_1, A_2, \cdots, A_N $のsuffixになるはずだから，後ろから順番にDPを計算していくべき．

さて，$ dp_i = A_i, A_{i+1}, \cdots, A_N $を非減少列にするために必要な操作回数と定義する．

$ dp_{i+1} $を用いて$ dp_i $を求めるには，$ dp_{i+1} $を求める際に$ A_{i+1} $に何回 (b) を適用したかを持っておきたいので，DPの次元を1つ増やす．

$ dp_{i, x} = dp_{i+1, j} + x $ (ただしjは$ A_{i} \times 4^x \leq A_{i+1} \times 4^j $を満たす最小のj)

このとき，$ 1 \leq A_i \leq 10^9 $で$ 10^9 \lt 4^{15} $なので，xは15まで考えていれば良い．それ以上操作する場合には，$ A_{i+1} $以降の値にももう1回ずつ操作する必要があるので，全部で $ (N-i+1) \times (x-15) $回操作回数が増えることになってしまう．

($ A_i = 10^9, A_{i+1}=1 $の場合を考えるとわかりやすい)

負の部分についても，同様にdpを考える．ただし，正の部分とは異なり数列$ A_1, A_2, \cdots, A_N $のprefixになるはずだから，前から順番にDPを計算していくべき．

正の部分と負の部分両方のDPが計算できたら，あとは正と負の境界をn通り試す．

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

int main() {
    ll n;
    cin >> n;
    vector<ll> a(n);
    for(int i=0;i<n;++i) cin >> a[i];

    ll pos[n][16], neg[n][16];
    for(int x=0;x<=15;++x) {
        pos[n-1][x] = x;
        neg[0][x] = x;
    }

    for(int i=n-2;i>=0;--i) {
        ll x4 = 1;
        for(int x=0;x<=15;++x) {
            int j = 0;
            ll j4 = 1;
            while(a[i] * x4 > a[i+1] * j4) {
                j4 *= 4;
                ++j;
            }
            if(j <= 15) {
                pos[i][x] = pos[i+1][j] + x;
            } else {
                pos[i][x] = pos[i+1][15] + (n-i-1) * (j-15) + x;
            }
            x4 *= 4;
        }
    }

    for(int i=1;i<n;++i) {
        ll x4 = 1;
        for(int x=0;x<=15;++x) {
            int j = 0;
            ll j4 = 1;
            while(a[i-1] * j4 < a[i] * x4) {
                j4 *= 4;
                ++j;
            }
            if(j <= 15) {
                neg[i][x] = neg[i-1][j] + x;
            } else {
                neg[i][x] = neg[i-1][15] + i * (j-15) + x;
            }
            x4 *= 4;
        }
    }

    ll ans = pos[0][0] * 2;
    for(int i=1;i<n;++i) {
        ans = min(ans, i + neg[i-1][0] * 2 + pos[i][0] * 2);
    }
    cout << ans << "\n";
}

所感

いやめっちゃ難しく感じた……．だけど解説放送見たらお気持ちが湧いてきたのでやはりりんごさんは神

NoiminのNoise

CADDi 2018 E - Negative Doubling

問題概要

解法概要

ソースコード

所感