Monotone Minima

components/monotone_minima.hpp · GitHub で見る

共通ページ

#include "lib/components/monotone_minima.hpp"

int n = 100, m = 100;
auto value = [](int row, int col) { return 1LL * (row - col) * (row - col); };
auto best = monotone_minima(n, m, [&](int row, int old_col, int new_col) {
    return value(row, new_col) < value(row, old_col);
});

関数	内容・返り値	計算量
monotone_minima(rows,columns,better)	行数・列数を指定し、各行の最良の列番号を vector<int> で返す	\(O(n+m\log n)\)、1 行: \(O(m)\)
monotone_minima(rows,column_ids,better)	vector<int> に並べた列番号を対象にし、各行の最良の列番号を返す	\(O(n+m\log n)\)、1 行: \(O(m)\)

better(row,old_col,new_col) は、その行で新しい列を選ぶときに true を返します。最小値なら <、最大値なら > で比較します。同値で false を返すと、同じ値を取る列のうち先の列を選びます。行列を保存せず、比較時に値を計算しても構いません。

選ばれる最良の列の位置が、行番号について広義単調増加することが条件です。最小値の列が単調なだけで使え、完全単調である必要はありません。完全単調行列には、比較回数が線形の SMAWK も使えます。条件の検査は行いません。

column_ids 版では、配列に並べた順を列の順として扱い、返り値は配列内の位置ではなく列番号です。列を絞った後の行列でも、選ばれる位置の単調性が必要です。

行数・列数は非負の int の範囲です。行があれば少なくとも 1 列が必要です。0 行は空配列を返します。0 行の場合や、1 列の場合は比較関数を呼びません。内部は幅優先の反復処理で、再帰や行列の構築は行いません。

行数を \(n\)、列数を \(m\) とし、比較を \(O(1)\) とします。\(n\ge2,m\ge1\) では \(O(n+m\log n)\) 時間、返り値を含め \(O(n)\) 空間です。返り値以外の作業空間は \(O(1)\) です。1 行は \(O(m)\) 時間、0 行は \(O(1)\) 時間・空間です。

検証コード

• test/monotone_minima.test.cpp

コード

#ifndef MONOTONE_MINIMA_HPP
#define MONOTONE_MINIMA_HPP

#include <algorithm>
#include <bit>
#include <cassert>
#include <cstddef>
#include <limits>
#include <vector>

namespace monotone_minima_detail {
template <class Better, class Column>
std::vector<int> solve(int rows, int columns, Better &better, Column column) {
	if (!rows) return {};
	if (columns == 1) return std::vector<int>(rows, column(0));
	std::vector<int> best(std::size_t(rows) + 1);
	best[rows] = columns - 1;
	for (int j = 1; j < columns; ++j)
		if (better(0, column(best[0]), column(j))) best[0] = j;
	for (unsigned step = std::bit_ceil(unsigned(rows)) >> 1; step; step >>= 1) {
		for (unsigned row = step; row < unsigned(rows); row += 2 * step) {
			int lo = best[row - step], hi = best[std::min(row + step, unsigned(rows))];
			int result = lo;
			for (int j = lo + 1; j <= hi; ++j)
				if (better(int(row), column(result), column(j))) result = j;
			best[row] = result;
		}
	}
	best.pop_back();
	for (auto &j : best) j = column(j);
	return best;
}
}

template <class Better>
std::vector<int> monotone_minima(int rows, int columns, Better better) {
	assert(rows >= 0 && columns >= 0 && (!rows || columns));
	return monotone_minima_detail::solve(rows, columns, better, [](int j) { return j; });
}

template <class Better>
std::vector<int> monotone_minima(int rows, const std::vector<int> &columns, Better better) {
	assert(rows >= 0 && columns.size() <= std::size_t(std::numeric_limits<int>::max()) && (!rows || !columns.empty()));
	return monotone_minima_detail::solve(rows, int(columns.size()), better, [&](int j) { return columns[j]; });
}

#endif

Back to top page