#1174674 (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:45:04
• 言語: C++23 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 912 ms / 2,000 ms
• コード長: 3,159 bytes
• コンパイル時間: 6,771 ms
• コンパイル使用メモリ: 676,444 KB
• 実行使用メモリ: 13,004 KB
• 最終ジャッジ日時: 2026-08-05 23:35:53
• 合計ジャッジ時間: 16,810 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_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{})
    };
    cout << setprecision(100) << static_cast<unsigned long>(num) / static_cast<long double>(den) << endl;
    return 0;
}