This documentation is automatically generated by online-judge-tools/verification-helper
$N \times N$ 下三角行列 $A$
各 $i$ について $\mathop {\rm arg \, min} \limits _ j A _ {i , j}$
大雑把に言えば、このアルゴリズムはある種の動的計画法を高速化するものである。 出力の値は $i$ の昇順に計算され、$A _ {i , j + 1}$ の値は $\mathop {\rm arg \, min} \limits _ k A _ {j, k}$ が計算された後にアクセス出来れば良い。 したがって $A _ {i , j}$ は ${\rm dp} \lbrack j \rbrack$ から ${\rm dp} \lbrack i + 1 \rbrack$ への遷移とみなすことが出来る。 SMAWK Algorithm を on-line な動的計画法に適用出来るよう工夫したものとも言える。 実際、アルゴリズムの内容も SMAWK Algorithm に類似している。
SMAWK Algorithm を参照せよ。 ただしこのページでは文献に合わせて、$\min$ による定義を採用している。
#include <functional>
#include <memory>
#include <vector>
template <class T> class larsch {
struct reduce_row;
struct reduce_col;
struct reduce_row {
int n;
std::function<T(int, int)> f;
int cur_row;
int state;
std::unique_ptr<reduce_col> rec;
reduce_row(int n_) : n(n_), f(), cur_row(0), state(0), rec() {
const int m = n / 2;
if (m != 0) {
rec = std::make_unique<reduce_col>(m);
}
}
void set_f(std::function<T(int, int)> f_) {
f = f_;
if (rec) {
rec->set_f([&](int i, int j) -> T { return f(2 * i + 1, j); });
}
}
int get_argmin() {
const int cur_row_ = cur_row;
cur_row += 1;
if (cur_row_ % 2 == 0) {
const int prev_argmin = state;
const int next_argmin = [&]() {
if (cur_row_ + 1 == n) {
return n - 1;
} else {
return rec->get_argmin();
}
}();
state = next_argmin;
int ret = prev_argmin;
for (int j = prev_argmin + 1; j <= next_argmin; j += 1) {
if (f(cur_row_, ret) > f(cur_row_, j)) {
ret = j;
}
}
return ret;
} else {
if (f(cur_row_, state) <= f(cur_row_, cur_row_)) {
return state;
} else {
return cur_row_;
}
}
}
};
struct reduce_col {
int n;
std::function<T(int, int)> f;
int cur_row;
std::vector<int> cols;
reduce_row rec;
reduce_col(int n_) : n(n_), f(), cur_row(0), cols(), rec(n) {}
void set_f(std::function<T(int, int)> f_) {
f = f_;
rec.set_f([&](int i, int j) -> T { return f(i, cols[j]); });
}
int get_argmin() {
const int cur_row_ = cur_row;
cur_row += 1;
const auto cs = [&]() -> std::vector<int> {
if (cur_row_ == 0) {
return {{0}};
} else {
return {{2 * cur_row_ - 1, 2 * cur_row_}};
}
}();
for (const int j : cs) {
while ([&]() {
const int size = cols.size();
return size != cur_row_ && f(size - 1, cols.back()) > f(size - 1, j);
}()) {
cols.pop_back();
}
if (cols.size() != n) {
cols.push_back(j);
}
}
return cols[rec.get_argmin()];
}
};
std::unique_ptr<reduce_row> base;
public:
larsch(int n, std::function<T(int, int)> f)
: base(std::make_unique<reduce_row>(n)) {
base->set_f(f);
}
int get_argmin() { return base->get_argmin(); }
};
/**
* @brief LARSCH Algorithm
* @docs docs/larsch.md
*/
#line 1 "algorithm/larsch.cpp"
#include <functional>
#include <memory>
#include <vector>
template <class T> class larsch {
struct reduce_row;
struct reduce_col;
struct reduce_row {
int n;
std::function<T(int, int)> f;
int cur_row;
int state;
std::unique_ptr<reduce_col> rec;
reduce_row(int n_) : n(n_), f(), cur_row(0), state(0), rec() {
const int m = n / 2;
if (m != 0) {
rec = std::make_unique<reduce_col>(m);
}
}
void set_f(std::function<T(int, int)> f_) {
f = f_;
if (rec) {
rec->set_f([&](int i, int j) -> T { return f(2 * i + 1, j); });
}
}
int get_argmin() {
const int cur_row_ = cur_row;
cur_row += 1;
if (cur_row_ % 2 == 0) {
const int prev_argmin = state;
const int next_argmin = [&]() {
if (cur_row_ + 1 == n) {
return n - 1;
} else {
return rec->get_argmin();
}
}();
state = next_argmin;
int ret = prev_argmin;
for (int j = prev_argmin + 1; j <= next_argmin; j += 1) {
if (f(cur_row_, ret) > f(cur_row_, j)) {
ret = j;
}
}
return ret;
} else {
if (f(cur_row_, state) <= f(cur_row_, cur_row_)) {
return state;
} else {
return cur_row_;
}
}
}
};
struct reduce_col {
int n;
std::function<T(int, int)> f;
int cur_row;
std::vector<int> cols;
reduce_row rec;
reduce_col(int n_) : n(n_), f(), cur_row(0), cols(), rec(n) {}
void set_f(std::function<T(int, int)> f_) {
f = f_;
rec.set_f([&](int i, int j) -> T { return f(i, cols[j]); });
}
int get_argmin() {
const int cur_row_ = cur_row;
cur_row += 1;
const auto cs = [&]() -> std::vector<int> {
if (cur_row_ == 0) {
return {{0}};
} else {
return {{2 * cur_row_ - 1, 2 * cur_row_}};
}
}();
for (const int j : cs) {
while ([&]() {
const int size = cols.size();
return size != cur_row_ && f(size - 1, cols.back()) > f(size - 1, j);
}()) {
cols.pop_back();
}
if (cols.size() != n) {
cols.push_back(j);
}
}
return cols[rec.get_argmin()];
}
};
std::unique_ptr<reduce_row> base;
public:
larsch(int n, std::function<T(int, int)> f)
: base(std::make_unique<reduce_row>(n)) {
base->set_f(f);
}
int get_argmin() { return base->get_argmin(); }
};
/**
* @brief LARSCH Algorithm
* @docs docs/larsch.md
*/