AtCoder ABC182 D Wandering 解

問題

考察

当然ながら愚直な全探索は $O(N^2)$ かかるので不可能。

任意回操作後のロボの位置は、事前にA[]の累積和cs[]を計算しておくことで、dp によって$O(N)$で計算できる。だから、(i-1)回目の操作終了後の位置を所与として、次の i 回目の合計 i 個の操作 $(+A_1,...,+A_i)$ を行う過程における位置 $p_i$ の最大値を高速に(遅くとも$O(\log N)$ で) 計算できれば良い。

この $p_i$ は、(i-1)回目の操作終了後の位置 $dp_{i-1}$ に、i 回目の操作における移動の最大幅を足すことで求められる。後者は、i 個の移動$(+A_1,...,+A_i)$ を順に行っていく際の累積和の最大値だから、$p_i = dp_{i-1}+\min_{k \le i} cs_k$ と計算できる。この右辺第二項(pmax[i]と呼ぶことにする)は、明らかに位置情報dp[]とは無関係に、累積和cs[]に対する漸化式として動的に$O(N)$で計算できる。

cs[]やpmax[]を事前に計算しておくことにより、全体の計算量は$O(N)$に収まる。

実装

以上の考察を素直に実装するだけ。

int main() {
    // read input
    auto n = in<ll>();
    auto a = vin<ll>(n);

    // cumulative sum
    vector<ll> cs(n, 0);
    cs[0]              = a[0];
    rep(i, 1, n) cs[i] = cs[i - 1] + a[i];

    // path max
    vector<ll> pmax(n, 0);
    pmax[0]              = max(0, a[0]);
    rep(i, 1, n) pmax[i] = max(pmax[i - 1], cs[i]);

    // calc by dp
    ll ans = max(0, a[0]);
    vector<ll> dp(n, 0);
    dp[0] = a[0];
    rep(i, 1, n) {
        chmax(ans, dp[i - 1] + pmax[i]);
        dp[i] = dp[i - 1] + cs[i];
    }
    // show
    print(ans);
}