有理数で二分探索
(Src/Utility/RationalBinarySearch.hpp)

• View this file on GitHub
• Last update: 2025-07-23 20:10:46+09:00
• Include: #include "Src/Utility/RationalBinarySearch.hpp"

概要

$N$ 以下の分母を持つ非負の有理数の集合上で二分探索を行い、 $f(\frac{a}{b})$ がTrueになる最大の $\frac{a}{b}$ と $f(\frac{a}{b})$ がFalseになる最小の $\frac{a}{b}$ を計算する。

$f$ は $f(\frac{0}{1}) = \text{T}, f(\frac{0}{1}(= \infty)) = \text{F}$ を満たす必要がある。

Verified with

• Test/AtCoder/abc333_g.test.cpp
• Test/LC/rational_approximation.test.cpp

Code

#pragma once

#include <cassert>
#include <concepts>
#include <utility>

namespace zawa {

template <class F, std::integral T>
requires std::predicate<F, T, T>
std::pair<std::pair<T, T>, std::pair<T, T>> RationalBinarySearch(F f, T n) {
    assert(f(0, 1) and !f(1, 0));
    auto dfs = [&](auto dfs, bool cur, T& p, T& q, T pp, T pq) -> void {
        if (p + pp > n or q + pq > n) return;
        if (f(p + pp, q + pq) == cur) {
            p += pp;
            q += pq;
            dfs(dfs, cur, p, q, pp << 1, pq << 1);
        }
        if (p + pp <= n and q + pq <= n and f(p + pp, q + pq) == cur) {
            p += pp;
            q += pq;
        }
    };
    T pl = 0, ql = 1, pr = 1, qr = 0;
    while (pl + pr <= n and ql + qr <= n) {
        dfs(dfs, true, pl, ql, pr, qr);
        dfs(dfs, false, pr, qr, pl, ql);
    }
    return std::pair{std::pair{pl, ql}, std::pair{pr, qr}};
}

} // namespace zawa

#line 2 "Src/Utility/RationalBinarySearch.hpp"

#include <cassert>
#include <concepts>
#include <utility>

namespace zawa {

template <class F, std::integral T>
requires std::predicate<F, T, T>
std::pair<std::pair<T, T>, std::pair<T, T>> RationalBinarySearch(F f, T n) {
    assert(f(0, 1) and !f(1, 0));
    auto dfs = [&](auto dfs, bool cur, T& p, T& q, T pp, T pq) -> void {
        if (p + pp > n or q + pq > n) return;
        if (f(p + pp, q + pq) == cur) {
            p += pp;
            q += pq;
            dfs(dfs, cur, p, q, pp << 1, pq << 1);
        }
        if (p + pp <= n and q + pq <= n and f(p + pp, q + pq) == cur) {
            p += pp;
            q += pq;
        }
    };
    T pl = 0, ql = 1, pr = 1, qr = 0;
    while (pl + pr <= n and ql + qr <= n) {
        dfs(dfs, true, pl, ql, pr, qr);
        dfs(dfs, false, pr, qr, pl, ql);
    }
    return std::pair{std::pair{pl, ql}, std::pair{pr, qr}};
}

} // namespace zawa

Back to top page