2020-02-06

CADDi 2018 E - Negative Doubling (黄色, 800 点)

AtCoder AtCoder800点累積和テク:左右両端からの累積和や累積結果を前処理ある値を固定して考える Greedy:ある量を決めると残りが決まっていく Greedy DP 添字のとりうる範囲がlogオーダー見積り大事操作最小回数・最小個数を求めるデータ構造テク：前処理 stack データ構造応用的な探索数列最適化テク:最適解の形を考える ARC-E ARC-like 黄色diff 累積和テク:累積和や累積結果を前処理しておく DP高速化:stackの活用操作をstackを用いて高速化する最適化問題

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

問題へのリンク

問題概要

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 つくらい考えられそう。

dp に幅をもたせる。つまり「dp[ i ][ j ] := 右 i 個分について、先頭を 4^j 倍する場合についての最小回数」という風にする。
スタックを使って対処する

(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] を 4¹⁵ 倍くらいしていたら、それにともなって A[N - i] をたとえ 4²⁰ 倍しないといけないことになったとしても、4¹⁵ 倍から以降は先ほどの「崖」がないといえる。つまり、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;
}

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

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