#1174676 (C++23) No.3604 Min of Max of Div of Sum

• 問題: No.3604 Min of Max of Div of Sum
• ユーザー: 259-Momone
• 提出日時: 2026-08-01 08:49:58
• 言語: C++23 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 1,019 ms / 2,000 ms
• コード長: 4,597 bytes
• コンパイル時間: 8,355 ms
• コンパイル使用メモリ: 698,800 KB
• 実行使用メモリ: 13,184 KB
• 最終ジャッジ日時: 2026-08-05 23:36:17
• 合計ジャッジ時間: 19,054 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_0

ファイルパターン	結果
sample	AC * 3
other	AC * 25

ソースコード

#include <bits/extc++.h>

// 準備: pair の和、スカラー倍
template <typename T, typename S>
std::pair<T, S> operator+(const std::pair<T, S>& lhs, const std::pair<T, S>& rhs) {
    return {lhs.first + rhs.first, lhs.second + rhs.second};
}

template <typename S, typename T>
std::pair<T, T> operator*(const S& lhs, const std::pair<T, T>& rhs) {
    return {lhs * rhs.first, lhs * rhs.second};
}

// Stern-Brocot Tree の探索
//   judge_function(a, b) は非負有理数から {true, false} への写像であって、
//   ある分子・分母ともに max_value 以下であるような有理数 x/y によって a/b と x/y の大小関係で true, false が定まるもの。
//   x/y を O(log max_value) 時間で求める。
template <typename Integer, typename Judge>
std::pair<Integer, Integer> stern_brocot_tree_search(Judge&& judge_function, const Integer& max_value) {
    std::pair<Integer, Integer> lower{0, 1}, upper{1, 0}, now{1, 1}; // 下界 0/1 上界 1/0
    while (true) {
        now = lower + upper;
        const auto now_judge{judge_function(now)};
        auto &from{now_judge ? lower : upper}, &to{now_judge ? upper : lower}; // from から to へ向かって潜っていく
        // 指数探索
        // 1. 上限を探索
        Integer L{1}, R{2};
        while (judge_function(from + R * to) == now_judge) {
            L *= 2;
            R *= 2;
            // max_value より下まで潜ったら、それ以降無限に潜る -> 答えは to (= from + ∞ * to)
            if ((from + L * to).first > max_value || (from + L * to).second > max_value)return to;
        }
        // 2. 二分探索
        while (L + 1 < R) {
            const auto M{(L + R) / 2};
            (judge_function(from + M * to) == now_judge ? L : R) = M;
        }
        from = from + L * to;
    }
}

#include <boost/multiprecision/cpp_int.hpp>
#include <boost/rational.hpp>

int main() {
    using namespace std;
    using bigint = boost::multiprecision::cpp_int;
    using bigrat = boost::rational<bigint>;

    unsigned N;
    cin >> N;
    vector<unsigned> A(N), B(N);
    for (auto&& a : A) cin >> a;
    for (auto&& b : B) cin >> b;
    const auto& [num, den]{
        stern_brocot_tree_search([N, &A, &B](const pair<bigint, bigint>& x) {
            vector<bigint> C(N);
            ranges::transform(A, B, begin(C), [&x](unsigned a, unsigned b) { return x.second * a - x.first * b; });
            vector<bigint> prefix_max(N), suffix_max(N);
            prefix_max.front() = C.front();
            for (const auto i : views::iota(1U, N))
                prefix_max[i] = max<bigint>(prefix_max[i - 1], 0) + C[i];
            for (const auto i : views::iota(0U, N - 1) | views::reverse)
                suffix_max[i] = max<bigint>(suffix_max[i + 1] + C[i + 1], 0);
            return ranges::all_of(views::zip_transform(plus{}, prefix_max, suffix_max), [](const bigint& a){return a >= 0;});
        }, max(ranges::fold_left(A, 0UL, plus{}), ranges::fold_left(B, 0UL, plus{})) + bigint{})
    };
    const auto rational_to_string{[](auto x, unsigned long dig = 100, bool round_up = false){
        using rational_type = decltype(x);
        using integer_type = typename rational_type::int_type;
        const integer_type pow10{"1" + string(dig, '0')};
        if(round_up && (x * pow10).numerator() % (x * pow10).denominator() != 0)x += rational_type{1, pow10};
        integer_type num{x.numerator()}, den{x.denominator()};
        string ret{};
        if(num < 0){
            ret += '-';
            num *= -1;
        }
        ret += integer_type(num / den).str();
        ret += ".";
        num %= den;
        for(unsigned long i{}; i < dig; ++i){
            ret += integer_type((num *= 10) / den).str();
            num %= den;
        }
        while(!empty(ret) && ret.back() == '0')ret.pop_back();
        if(ret.back() == '.')ret.pop_back();
        return ret;
    }};
    const auto error_bound{[](auto x, unsigned long dig, bool is_upper = true, unsigned long coef = 1){
        using rational_type = decltype(x);
        using integer_type = typename rational_type::int_type;
        const integer_type pow10{"1" + string(dig, '0')};
        if(is_upper)return max({x + rational_type(coef, pow10), x * rational_type(pow10 + coef, pow10), x * rational_type(pow10 - coef, pow10)});
        else return min({x - rational_type(coef, pow10), x * rational_type(pow10 + coef, pow10), x * rational_type(pow10 - coef, pow10)});
    }};
    cout << rational_to_string(error_bound(bigrat{num, den}, 6, false), 100, true) << endl;
    return 0;
}