SMAWK

components/smawk.hpp · GitHub で見る

共通ページ

#include "lib/components/smawk.hpp"

auto value = [](int row, int col) { return (row - col) * (row - col); };
auto best = smawk(3, 4, [&](int row, int old_col, int new_col) {
	return value(row, new_col) < value(row, old_col);
}); // {0,1,2}

操作	内容・返り値	計算量
smawk(rows,columns,better)	行数・列数を指定し、各行の最良の列番号を返す	\(O(n+m)\)
smawk(rows,column_ids,better)	調べる列番号を順に指定する版	\(O(n+m)\)

完全単調行列の各行の最小値を取る列番号を返します。行列は配列として渡さず、比較関数内で必要な値を計算します。返り値 best[row] がその行で選ばれた列番号です。比較関数は新しい列がより良いときに true を返し、同値なら先の列を残します。

columns は列数、または調べる列番号を順に並べた std::vector<int> です。後者ではその順序で完全単調とします。行がある場合は少なくとも 1 列必要です。

各行の最良の列が単調でも、完全単調とは限りません。その場合は、同じ比較関数の形で使える Monotone Minima を使います。

行数を \(n\)、列数を \(m\) として時間・空間は \(O(n+m)\) です。比較は \(O(1)\) とします。

検証コード

• test/min_plus_concave.test.cpp
• test/min_plus_convex.test.cpp
• test/min_plus_convex_convex.test.cpp
• test/smawk.test.cpp

コード

#ifndef SMAWK_HPP
#define SMAWK_HPP

#include <algorithm>
#include <cassert>
#include <cstddef>
#include <numeric>
#include <vector>

template <class Better>
std::vector<int> smawk(int length, const std::vector<int> &columns, Better better) {
	assert(length >= 0 && (!length || !columns.empty()));
	if (!length) return {};
	std::vector<int> best(length);
	auto solve = [&](auto &&self, std::size_t first, std::size_t stride, const std::vector<int> &cols) -> void {
		int rows = (length - 1 - first) / stride + 1;
		std::vector<int> reduced;
		reduced.reserve(std::min<std::size_t>(rows, cols.size()));
		for (int col : cols) {
			while (!reduced.empty() && better(first + (int(reduced.size()) - 1) * stride, reduced.back(), col)) reduced.pop_back();
			if (int(reduced.size()) < rows) reduced.push_back(col);
		}
		if (rows > 1) self(self, first + stride, stride * 2, reduced);
		std::size_t left = 0;
		for (std::size_t row = first; row < std::size_t(length); row += 2 * stride) {
			std::size_t right = left;
			if (row + stride < std::size_t(length))
				while (reduced[right] != best[row + stride]) ++right;
			else right = reduced.size() - 1;
			best[row] = reduced[left];
			for (std::size_t i = left + 1; i <= right; ++i)
				if (better(row, best[row], reduced[i])) best[row] = reduced[i];
			left = right;
		}
	};
	solve(solve, 0, 1, columns);
	return best;
}

template <class Better>
std::vector<int> smawk(int rows, int columns, Better better) {
	assert(columns >= 0);
	std::vector<int> cols(columns);
	std::iota(cols.begin(), cols.end(), 0);
	return smawk(rows, cols, better);
}

#endif

Back to top page