SMAWK (dp/smawk.hpp)

全単調行列の各行について、最適な列を線形時間で求める。行列の要素そのものを保持せず、2 列の優劣を判定する関数だけを受け取る。

smawk

template <typename F>
vector<int> smawk(int H, int W, F comp)

各行の最適な列番号を返す。comp(i, j, k) は、行 i において列 k が列 j より真に良いとき true を返すものとする。同値な候補では左側の列を選ぶ。

引数

H: 行数
W: 列数
comp: 2 列の優劣を判定する関数

戻り値

長さ $H$ の配列を返し、その第 $i$ 要素は行 $i$ の最適な列番号である。$W = 0$ の場合は、すべての要素が $-1$ となる。

制約

$0 \leq H$
$0 \leq W$
行列が comp の定める順序について全単調である

計算量

時間: $O(H + W)$ 回の comp 呼び出し
空間: $O(H + W)$

参考文献

Aggarwal, Klawe, Moran, Shor, Wilber, Geometric Applications of a Matrix-Searching Algorithm

Required by

Verified with

Code

#pragma once

#include <algorithm>
#include <numeric>
#include <vector>

template <typename F>
std::vector<int> smawk(int H, int W, F comp) {
  std::vector<int> ret(H, -1);
  if (H == 0 || W == 0) return ret;

  auto dfs = [&](auto&& self, const std::vector<int>& rows,
                 const std::vector<int>& cols) -> void {
    if (rows.empty()) return;
    std::vector<int> reduced;
    reduced.reserve(std::min(rows.size(), cols.size()));
    for (int c : cols) {
      while (!reduced.empty()) {
        int r = rows[reduced.size() - 1];
        int old_c = reduced.back();
        if (comp(r, old_c, c)) {
          reduced.pop_back();
        } else {
          break;
        }
      }
      if (reduced.size() < rows.size()) reduced.emplace_back(c);
    }

    std::vector<int> odd_rows;
    odd_rows.reserve(rows.size() / 2);
    for (int i = 1; i < static_cast<int>(rows.size()); i += 2) {
      odd_rows.emplace_back(rows[i]);
    }
    self(self, odd_rows, reduced);

    int left = 0;
    for (int i = 0; i < static_cast<int>(rows.size()); i += 2) {
      int right = static_cast<int>(reduced.size()) - 1;
      if (i + 1 < static_cast<int>(rows.size())) {
        right = left;
        while (reduced[right] != ret[rows[i + 1]]) ++right;
      }
      int best = left;
      for (int p = left + 1; p <= right; ++p) {
        if (comp(rows[i], reduced[best], reduced[p])) best = p;
      }
      ret[rows[i]] = reduced[best];
      left = right;
    }
  };

  std::vector<int> rows(H), cols(W);
  std::iota(rows.begin(), rows.end(), 0);
  std::iota(cols.begin(), cols.end(), 0);
  dfs(dfs, rows, cols);
  return ret;
}

#line 2 "dp/smawk.hpp"

#include <algorithm>
#include <numeric>
#include <vector>

template <typename F>
std::vector<int> smawk(int H, int W, F comp) {
  std::vector<int> ret(H, -1);
  if (H == 0 || W == 0) return ret;

  auto dfs = [&](auto&& self, const std::vector<int>& rows,
                 const std::vector<int>& cols) -> void {
    if (rows.empty()) return;
    std::vector<int> reduced;
    reduced.reserve(std::min(rows.size(), cols.size()));
    for (int c : cols) {
      while (!reduced.empty()) {
        int r = rows[reduced.size() - 1];
        int old_c = reduced.back();
        if (comp(r, old_c, c)) {
          reduced.pop_back();
        } else {
          break;
        }
      }
      if (reduced.size() < rows.size()) reduced.emplace_back(c);
    }

    std::vector<int> odd_rows;
    odd_rows.reserve(rows.size() / 2);
    for (int i = 1; i < static_cast<int>(rows.size()); i += 2) {
      odd_rows.emplace_back(rows[i]);
    }
    self(self, odd_rows, reduced);

    int left = 0;
    for (int i = 0; i < static_cast<int>(rows.size()); i += 2) {
      int right = static_cast<int>(reduced.size()) - 1;
      if (i + 1 < static_cast<int>(rows.size())) {
        right = left;
        while (reduced[right] != ret[rows[i + 1]]) ++right;
      }
      int best = left;
      for (int p = left + 1; p <= right; ++p) {
        if (comp(rows[i], reduced[best], reduced[p])) best = p;
      }
      ret[rows[i]] = reduced[best];
      left = right;
    }
  };

  std::vector<int> rows(H), cols(W);
  std::iota(rows.begin(), rows.end(), 0);
  std::iota(cols.begin(), cols.end(), 0);
  dfs(dfs, rows, cols);
  return ret;
}