test/src/optimization/alien_dp/arc168_e_2.test.cpp

• View this file on GitHub
• Last update: 2024-01-30 21:41:27+09:00
• Problem: https://atcoder.jp/contests/arc168/tasks/arc168_e

Depends on

• Alien Dp (library/optimization/alien_dp.hpp)

Code

#define PROBLEM "https://atcoder.jp/contests/arc168/tasks/arc168_e"

#include "library/optimization/alien_dp.hpp"


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


int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, k;
    long long s;
    std::cin >> n >> k >> s;

    std::vector<long long> a(n);
    for (auto& e : a) {
        std::cin >> e;
    }

    std::vector<long long> sa(n + 1);
    for (int i = 0; i < n; ++i) {
        sa[i + 1] = sa[i] + a[i];
    }

    std::vector<int> max_l(n + 1);
    for (int r = 0; r <= n; ++r) {
        max_l[r] = int(std::upper_bound(sa.begin(), sa.end(), sa[r] - s) - sa.begin()) - 1;
    }

    constexpr long long inf = 1LL << 60;

    auto solve = [&](int p) {
        std::vector<std::pair<long long, int>> dp(n + 1, { inf, n + 1 });
        dp[0] = { 0LL, 0 };
        for (int i = 1; i <= n; ++i) {
            dp[i] = dp[i - 1];
            if (int j = max_l[i]; j >= 0) {
                dp[i] = std::min(dp[i], std::pair{ dp[j].first + (i - j - 1) - p, dp[j].second + 1 });
            }
        }
        return dp[n].first;
    };

    int ok = 0, ng = k + 1;
    while (ng - ok > 1) {
        int x = (ok + ng) / 2;
        (suisen::alien_convex<long long>(x, 0, n, solve) <= n - k ? ok : ng) = x;
    }
    std::cout << ok << std::endl;
}

#line 1 "test/src/optimization/alien_dp/arc168_e_2.test.cpp"
#define PROBLEM "https://atcoder.jp/contests/arc168/tasks/arc168_e"

#line 1 "library/optimization/alien_dp.hpp"



#include <type_traits>
#include <utility>

namespace suisen {
    /**
     * @brief evaluates f(x) (f: convex)
     * @param g p -> inf(f(x)-px)
     */
    template <typename Cost, typename DP, std::enable_if_t<std::is_invocable_r_v<Cost, DP, Cost>, std::nullptr_t> = nullptr>
    Cost alien_convex(int x, Cost min_slope, Cost max_slope, DP g) {
        // x <= max (argmin (f(x)-rx))
        Cost lp = min_slope - 1, rp = max_slope + 1;
        while (rp - lp > 1) {
            Cost p = (lp + rp) / 2;
            // xp: max (argmin f(x)-px) (= min (argmin f(x)-(p+1)x))
            int xp = g(p) - g(p + 1);
            (x <= xp ? rp : lp) = p;
        }
        return g(rp) + Cost(rp) * x;
    }
    /**
     * @brief evaluates f(x) (f: convex)
     * @param g p -> { inf(f(x)-px), min argmin(f(x)-px) }
     */
    template <typename Cost, typename DP, std::enable_if_t<std::is_invocable_r_v<std::pair<Cost, int>, DP, Cost>, std::nullptr_t> = nullptr>
    Cost alien_convex(int x, Cost min_slope, Cost max_slope, DP g) {
        Cost lp = min_slope - 1, rp = max_slope + 1;
        while (rp - lp > 1) {
            Cost p = (lp + rp) / 2;
            // g(p).second: min (argmin f(x)-px)
            (g(p).second <= x ? lp : rp) = p;
        }
        return g(lp).first + Cost(lp) * x;
    }

    /**
     * @brief evaluates f(x) (f: concave)
     * @param g p -> sup(f(x)-px)
     */
    template <typename Cost, typename DP, std::enable_if_t<std::is_invocable_r_v<Cost, DP, Cost>, std::nullptr_t> = nullptr>
    Cost alien_concave(int x, Cost min_slope, Cost max_slope, DP g) {
        // min (argmax f(x)-rx) <= x
        Cost lp = min_slope - 1, rp = max_slope + 1;
        while (rp - lp > 1) {
            Cost p = (lp + rp) / 2;
            // xp: min (argmax f(x)-px) (= max (argmax f(x)-(p+1)x))
            int xp = g(p) - g(p + 1);
            (xp <= x ? rp : lp) = p;
        }
        return g(rp) + Cost(rp) * x;
    }
    /**
     * @brief evaluates f(x) (f: concave)
     * @param g p -> { sup(f(x)-px), max argmax(f(x)-px) }
     */
    template <typename Cost, typename DP, std::enable_if_t<std::is_invocable_r_v<std::pair<Cost, int>, DP, Cost>, std::nullptr_t> = nullptr>
    Cost alien_concave(int x, Cost min_slope, Cost max_slope, DP g) {
        // x <= max (argmax f(x)-lx)
        Cost lp = min_slope - 1, rp = max_slope + 1;
        while (rp - lp > 1) {
            Cost p = (lp + rp) / 2;
            // g(p).second: max (argmax f(x)-px)
            (x <= g(p).second ? lp : rp) = p;
        }
        return g(lp).first + Cost(lp) * x;
    }
} // namespace suisen



#line 4 "test/src/optimization/alien_dp/arc168_e_2.test.cpp"


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


int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, k;
    long long s;
    std::cin >> n >> k >> s;

    std::vector<long long> a(n);
    for (auto& e : a) {
        std::cin >> e;
    }

    std::vector<long long> sa(n + 1);
    for (int i = 0; i < n; ++i) {
        sa[i + 1] = sa[i] + a[i];
    }

    std::vector<int> max_l(n + 1);
    for (int r = 0; r <= n; ++r) {
        max_l[r] = int(std::upper_bound(sa.begin(), sa.end(), sa[r] - s) - sa.begin()) - 1;
    }

    constexpr long long inf = 1LL << 60;

    auto solve = [&](int p) {
        std::vector<std::pair<long long, int>> dp(n + 1, { inf, n + 1 });
        dp[0] = { 0LL, 0 };
        for (int i = 1; i <= n; ++i) {
            dp[i] = dp[i - 1];
            if (int j = max_l[i]; j >= 0) {
                dp[i] = std::min(dp[i], std::pair{ dp[j].first + (i - j - 1) - p, dp[j].second + 1 });
            }
        }
        return dp[n].first;
    };

    int ok = 0, ng = k + 1;
    while (ng - ok > 1) {
        int x = (ok + ng) / 2;
        (suisen::alien_convex<long long>(x, 0, n, solve) <= n - k ? ok : ng) = x;
    }
    std::cout << ok << std::endl;
}

Back to top page