けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

CADDi 2018 E - Negative Doubling (800 点)

こういうのを確実に...

問題へのリンク

問題概要

1 以上の整数からなる長さ  N の数列  A_{1}, A_{2}, \dots, A_{N} が与えられる。この数列に対して、以下の操作を好きな回数だけ好きな順序で行うことで広義単調増加となるようにしたい。最小回数を求めよ。

  •  N 個の整数から 1 つ選んで -2 倍する

制約

  •  N \le 2 \times 10^{5}
  •  1 \le A_{i} \le 10^{9}

考えたこと

単調増加ということは

  • 最初の k 個はマイナス
  • 残りの N-k 個はプラス

という感じになっていることになる。よってこの k を全探索したい。k を決めてしまえば Greedy に解くことができる。後半のプラスの方でいえば、まず先頭の値はそのままに 2 番目の値をなるべく小さい範囲で先頭の値以上になるようにする...これを繰り返す。

これでとりあえず  O(N^{2}) にはなった。ここから高速化を頑張る。

左右から前処理

こういうのはあらかじめ、「左 k 個分」「右 k 個分」についての結果をそれおれ前処理すれば OK。今回は左のマイナスの部分については、符号反転して reverse することで右から扱うのと同じになるので、「右 k 個分」について考えれば十分。そこでこんな感じのことをしたくなる

  • dp[ i ] := 右 i 個分を単調増加とするのに必要な最小回数

一見すると、dp[ i ] から dp[ i + 1 ] への更新は、s = a[N - i - 1] と t = a[N - i] とに対して s <= t となるまで t を増やす回数を d として dp[ i + 1 ] = dp[ i ] + d × i とすればよさそうに思えてくる。だがこれは違う。

たとえば、5, 3, 4, 21, 22, 23 とかに対して、dp[ 5 ] から dp[ 6 ] に更新しようとしたとき、(3, 4) のところだけを 4 倍すれば、5, 12, 15, 21, 22, 23 になってうまくいく。だが「(3, 4) のところだけ」という部分をいかんともしがたい。こういう「前方を倍にしても後方はそのままでもよいという」に対する対策が必要となる。

これに対する対策はざっくり 2 つくらい考えられそう。

  1. dp に幅をもたせる。つまり「dp[ i ][ j ] := 右 i 個分について、先頭を 4j 倍する場合についての最小回数」という風にする。

  2. スタックを使って対処する

(1) dp に幅をもたせる

  • dp[ i ][ j ] := 右 i 個分について、先頭を  4^{j} 倍する場合についての最小回数

としておく。これを  j \le 15 くらいまでやれば OK。なぜなら、 A の値はたかだか  10^{9} なので、 A_{i} A_{i+1} との 4 を底とした差分はたかだか 15 くらいだからだ。

そして、A[N - i - 1] を 415 倍くらいしていたら、それにともなって A[N - i] をたとえ 420 倍しないといけないことになったとしても、415 倍から以降は先ほどの「崖」がないといえる。つまり、dp[ i ][ 15 ] に、5 × 2 × i を足せば OK という感じになる。

この方針は、ちょっとデバッグしづらいのが辛い。。。
僕は適当なランダム最大ケースを作って、DP 幅を 3〜16 で変えたりしてみた。3 と 16 とでは変わるけど 15 と 16 とで変わらないあたりで大丈夫かな...と判断した。

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const long long INF = 1LL<<60;
const int MAX = 16;
int N;
vector<long long> A;

vector<vector<long long>> calc(const vector<long long> &a, int offset = 0) {
    vector<vector<long long>> dp(N+1, vector<long long>(MAX, INF));
    for (int j = 0; j < MAX; ++j) dp[0][j] = 0, dp[1][j] = j*2 + offset;
    for (int i = 1; i < N; ++i) {
        long long s = a[N-i-1];
        for (int j = 0; j < MAX; ++j) {
            long long t = a[N-i];
            int need = 0;
            while (s > t) ++need, t *= 4;
            long long add = 0;
            if (need >= MAX) {
                add = (need - MAX + 1) * i * 2;        
                need = MAX-1;
            }
            chmin(dp[i+1][j], dp[i][need] + j * 2 + add + offset);
            s *= 4;
        }
    }
    return dp;
}

long long solve() {
    const auto &right = calc(A);
    reverse(A.begin(), A.end());
    const auto &left = calc(A, 1);
    long long res = INF;
    for (int i = 0; i <= N; ++i) chmin(res, left[i][0] + right[N-i][0]);
    return res;
}

int main() {
    cin >> N;
    A.resize(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    cout << solve() << endl;
}

(2) スタックを使う

スタックを使えばどこに崖があるのかを管理しながら進めていくことができる。こっちのが確実かも。

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const long long INF = 1LL<<60;
const int MAX = 16;
int N;
vector<long long> A;

vector<long long> calc(const vector<long long> &a, int offset = 0) {
    stack<pair<int,int>> st;
    vector<long long> res(N+1, 0);
    res[1] = offset;
    for (int i = 1; i < N; ++i) {
        long long s = a[N-i-1], t = a[N-i];
        long long need = 0;
        while (s > t) ++need, t *= 4;

        if (need) {
            long long add = 0;
            while (!st.empty() && need) {
                auto gake = st.top(); st.pop();
                if (gake.second >= need) {
                    add += need * (i - gake.first) * 2;
                    gake.second -= need;
                    need = 0;
                    if (gake.second) st.push({gake.first, gake.second});
                }
                else {
                    add += gake.second * (i - gake.first) * 2;
                    need -= gake.second;
                }
            }
            if (need) add += need * i * 2;
            res[i+1] = res[i] + add + offset;
        }
        else {
            long long new_gake = 0;
            while (s * 4 <= t) ++new_gake, s *= 4;
            st.push({i, new_gake});
            res[i+1] = res[i] + offset;
        }
    }
    return res;
}

long long solve() {
    const auto &right = calc(A);
    reverse(A.begin(), A.end());
    const auto &left = calc(A, 1);
    long long res = INF;
    for (int i = 0; i <= N; ++i) chmin(res, left[i] + right[N-i]);
    return res;
}

int main() {
    cin >> N;
    A.resize(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    cout << solve() << endl;
}