library_for_python

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub Kazun1998/library_for_python

:warning: General Binary Search
(Binary_Search/General.py)

Outline

整数 (実数) $x$ に関する条件 $\operatorname{cond}(x)$ について, 以下を求める.

Theory

$X$ は $\mathbb{Z}$ か $\mathbb{R}$ であるとする. $X$ 上の条件 $\operatorname{cond}: X \to \{\mathbb{T}, \mathbb{F}\}$ について, 以下を定義する.

$X=\mathbb{Z}$ とする. このとき, 単調増加である $\operatorname{cond}$ に対して, $\operatorname{cond}(x)=\mathbb{T}$ となる最小の $x \in \mathbb{Z}$ を $X$ として, $X$ を求める.

  1. $L,R \in \mathbb{Z}$ を $\operatorname{cond}(L)=\mathbb{F}, \operatorname{cond}(R)=\mathbb{T}$ であるとする. このとき, $L \lt X \leq R$ が保証されている.
  2. $R-L>1$ である限り, 以下を繰り返し行う.
    • $C:=\left \lfloor \dfrac{L+R}{2} \right \rfloor$ とする.
    • $\operatorname{cond}(C)=\mathbb{T}$ ならば, $L \lt X \leq C$ であることが分かる. よって, $R \gets C$ とする.
    • $\operatorname{cond}(C)=\mathbb{F}$ ならば, $C \lt X \leq L$ であることが分かる. よって, $L \gets C$ とする.
  3. $R-L>1$ のとき, 初期値の定め方から, $R-L=1$ である. よって, $L \lt X \leq R$ となる整数 $X$ は $X=R$ に限られる. 従って, $R$ を出力すれば良い.

$\operatorname{cond}$ が単調減少の場合も同様であり, $X=\mathbb{R}$ の場合も $C:=\dfrac{L+R}{2}$ と変更すればよい. ただし, $X=\mathbb{R}$ の場合は厳密に求めることは不可能であり, ある程度の誤差の範囲で求めることになる.

また, $L, R$ は自分で見つける必要があり, $L,R$ が最初に満たすべき条件 (単調増加か単調減少かでかわる) を満たしていない場合は例外処理となる (特に $\operatorname{cond}(L)=\operatorname{cond}(R)=\mathbb{F}$) のとき.

Code

def General_Binary_Increase_Search_Integer(L: int, R: int, cond, default = None) -> int:
    """ 条件式が単調増加であるとき, 整数上で二部探索を行い, cond(x) が真になる最小の整数 x を求める.

    Args:
        L (int): 解の下限
        R (int): 解の上限
        cond (Callable[[int], bool]): 条件(1変数関数, 広義単調増加を満たす)
        default (Any, optional): R で条件を満たさない (つまり, [L, R] 上では常に偽) ときの返り値. Defaults to None.

    Returns:
        int: cond(x) が真になる最小の整数 x
    """
    if not cond(R):
        return default

    if cond(L):
        return L

    R += 1
    while R - L>1:
        C = L + (R - L) // 2
        if cond(C):
            R = C
        else:
            L = C
    return R

def General_Binary_Decrease_Search_Integer(L: int, R: int, cond, default = None) -> int:
    """ 条件式が単調減少であるとき, 整数上で二部探索を行い, cond(x) が真になる最大の整数 x を求める.

    Args:
        L (int): 解の下限
        R (int): 解の上限
        cond (Callable[[int], bool]): 条件(1変数関数, 広義単調減少を満たす)
        default (Any, optional): L で条件を満たさない (つまり, [L, R] 上では常に偽) ときの返り値. Defaults to None.

    Returns:
        int: cond(x) が真になる最小の整数 x
    """

    if not cond(L):
        return default

    if cond(R):
        return R

    L -= 1
    while R - L > 1:
        C = L + (R - L) // 2
        if cond(C):
            L = C
        else:
            R = C
    return L

def General_Binary_Increase_Search_Real(L: float, R: float, cond, trial: int, default: float = None) -> float:
    """ 条件式 cond が単調増加であるとき, 実数上での cond に関する二分探索を行い, cond(x) が真になる最小の実数 x の近似値を求める.

    Args:
        L (float): 下限
        R (float): 上限
        cond (Callable[[float], bool]): 条件式 (単調増加)
        trial (int): 判定回数の最大値
        default (float, optional): cond(R) が偽になるときの返り値. Defaults to None.

    Returns:
        float: cond(x) が最小になる実数 x の近似値
    """

    # [L, R] で挟めない場合を先に処理する.
    if not cond(R):
        return default

    if cond(L):
        return L

    for _ in range(trial):
        C = L + (R - L) / 2
        if cond(C):
            R = C
        else:
            L = C

    return (L + R) / 2

def General_Binary_Decrease_Search_Real(L: float, R: float, cond, trial: int, default: float = None) -> float:
    """ 条件式 cond が単調減少であるとき, 実数上での cond に関する二分探索を行い, cond(x) が真になる最大の実数 x の近似値を求める.

    Args:
        L (float): 下限
        R (float): 上限
        cond (Callable[[float], bool]): 条件式 (単調増加)
        trial (int): 判定回数の最大値
        default (float, optional): cond(L) が偽になるときの返り値. Defaults to None.

    Returns:
        float: cond(x) が最大になる実数 x の近似値
    """

    # [L, R] で挟めない場合を先に処理する.

    if not cond(L):
        return default

    if cond(R):
        return R

    for _ in range(trial):
        C = L + (R - L) / 2
        if cond(C):
            L = C
        else:
            R = C

    return (L + R) / 2
Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError
Back to top page