Monotone Minima
(Monotone/Monotone_Minima.py)

• View this file on GitHub
• Last update: 2025-06-01 12:50:15+09:00

Outline

$N$ 行 $M$ 列の行列 $A = (a_{i,j})$ が Monotone であるとは,

\[\min \left(\operatorname*{argmin}_{0 \leq j < M} a_{0,j} \right) \leq \min \left(\operatorname*{argmin}_{0 \leq j < M} a_{1,j} \right) \leq \dots \leq \min \left(\operatorname*{argmin}_{0 \leq j < M} a_{N-1,j} \right)\]

を満たすことである.

このとき, $0 \leq i < N$ それぞれに対する

\[\min \left(\operatorname*{argmin}_{0 \leq j < M} a_{i,j} \right)\]

を合計で $O(N + M \log N)$ 時間で求める.

Contents

Monotone_Minima(N: int, M: int, eval: Callable[[int, int], int]) -> list[int]

• Monotone な行列 $A = (a_{i,j})$ に対して, 各 $0 \leq i < N$ に対する $\displaystyle \min \left(\operatorname*{argmin}_{0 \leq j < M} a_{i,j} \right)$ を求める.
• 引数
  • $N$: 行数
  • $M$: 列数
  • $\textrm{eval}$: $a_{i,j} = \textrm{eval}(i,j)$ を満たす $2$ 変数関数
• 計算量
  • $O(N + M \log N)$ 時間

Code

def Monotone_Minima(N: int, M: int, eval) -> list[int]:
    """ N 行 M 列の行列 A の第 (i, j) 要素が eval(i, j) であり, 以下の単調性を満たすとする.
        f(i) := min argmin_{j} A(i, j) としたとき, f(0) <= f(1) <= ... <= f(M - 1) が成り立つ.
    このとき, 0 <= i < N に対して, f(i) を求める.

    Args:
        N (int): 行の数
        M (int): 列の数
        eval (Callable[[int, int], int]): 第 (i, j) 要素が eval(i, j) になる.

    Returns:
        list[int]: 第 i 要素が f(i) である長さ N のリスト
    """
    res = [-1] * N
    stack = [(0, N, 0, M)]

    while stack:
        u, d, l, r = stack.pop()

        if d - u < 1:
            continue

        i = (u + d) // 2
        j = min(range(l, r), key = lambda j: eval(i, j))

        res[i] = j

        stack.append((u, i, l, j + 1))
        stack.append((i + 1, d, j, r))

    return res

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.13.5/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.5/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page