cp-library

C++ Library for Competitive Programming

View the Project on GitHub emthrm/cp-library

:heavy_check_mark: Knuth–Yao speedup
(include/emthrm/dynamic_programming/knuth_yao_speedup.hpp)

$i \leq j$ を満たす $i, j \in \lbrace 1, 2, \ldots, n \rbrace$ で定義される二変数関数 $w(i, j)$ を考える。

とき、

\[c(i, j) \mathrel{:=} \begin{cases} 0 & (i = j), \\ \min_{i < k \leq j} \lbrace c(i, k - 1) + c(k, j) \rbrace + w(i, j) & (i < j) \end{cases}\]

で定義される $c$ に対して $c(i, j)$ ($1 \leq i \leq j \leq n$) を $O(n^2)$ 時間・領域で計算できる。

convex quadrangle inequality

$i \leq j$ を満たす $i, j$ で定義される二変数関数 $f(i, j)$ を考える。$i \leq i^\prime \leq j \leq j^\prime$ を満たす任意の $i, i^\prime, j, j^\prime$ に対して $f(i, j) + f(i^\prime, j^\prime) \geq f(i^\prime, j) + f(i, j^\prime)$ が成り立つならば、$f$ は convex quadrangle inequality を満たすと呼ぶ。

concave quadrangle inequality

$i \leq j$ を満たす $i, j$ で定義される二変数関数 $f(i, j)$ を考える。$i \leq i^\prime \leq j \leq j^\prime$ を満たす任意の $i, i^\prime, j, j^\prime$ に対して $f(i, j) + f(i^\prime, j^\prime) \leq f(i^\prime, j) + f(i, j^\prime)$ が成り立つならば、$f$ は concave quadrangle inequality を満たすと呼ぶ。

Monge property

$m \times n$ 型行列 $A$ を考える。$1 \leq i < i^\prime \leq m,\ 1 \leq j < j^\prime \leq n$ を満たす任意の $i, i^\prime \in \lbrace 1, 2, \ldots, m \rbrace,\ j, j^\prime \in \lbrace 1, 2, \ldots, n \rbrace$ に対して $A{\lbrack i, j^\prime \rbrack} + A{\lbrack i^\prime, j \rbrack} \geq A{\lbrack i, j \rbrack} + A{\lbrack i^\prime, j^\prime \rbrack}$ が成り立つという性質を Monge property と呼ぶ。Monge property を満たす $A$ は Monge matrix である。

ここで $m \times n$ 型行列 $A$ に対して、以下の二つは同値である。

Monge matrix は totally monotone である。逆は必ずしも成り立つとは限らない。

monotone

$m \times n$ 型行列 $A$ を考える。任意の $i \in \lbrace 1, 2, \ldots, m \rbrace$ に対して $j_i \in \mathrm{argmin}{\lbrace A{\lbrack i, j \rbrack} \mid j \in \lbrace 1, 2, \ldots, n \rbrace \rbrace}$ のとり方を一つ定める。$i < i^\prime$ を満たす任意の $i, i^\prime \in \lbrace 1, 2, \ldots, m \rbrace$ に対して $j_i \leq j_{i^\prime}$ が成り立つならば、$A$ は monotone であると呼ぶ。

totally monotone

$m \times n$ 型行列 $A$ に対して、以下の三つは同値である。

時間計算量

$O(N^2)$

仕様

名前 戻り値
template <typename T>
std::vector<std::vector<T>> knuth_yao_speedup(const std::vector<std::vector<T>>& w, const T inf); 		二変数関数 $w$ に対して上で定義した $f$

参考文献

Monge property

TODO

Submissons

https://atcoder.jp/contests/kupc2012/submissions/30174381

Verified with

Code

#ifndef EMTHRM_DYNAMIC_PROGRAMMING_KNUTH_YAO_SPEEDUP_HPP_
#define EMTHRM_DYNAMIC_PROGRAMMING_KNUTH_YAO_SPEEDUP_HPP_

#include <algorithm>
#include <vector>

namespace emthrm {

template <typename T>
std::vector<std::vector<T>> knuth_yao_speedup(
    const std::vector<std::vector<T>>& w, const T inf) {
  const int n = w.size();
  std::vector<std::vector<T>> dp(n, std::vector<T>(n, inf));
  if (n == 0) [[unlikely]] return dp;
  std::vector<std::vector<int>> argmin(n, std::vector<int>(n, -1));
  for (int j = 0; j < n; ++j) {
    dp[j][j] = 0;
    argmin[j][j] = j;
    for (int i = j - 1; i >= 0; --i) {
      const int right = std::min(j - 1, argmin[i + 1][j]);
      for (int k = argmin[i][j - 1]; k <= right; ++k) {
        const T tmp = dp[i][k] + dp[k + 1][j];
        if (tmp < dp[i][j]) {
          dp[i][j] = tmp;
          argmin[i][j] = k;
        }
      }
      dp[i][j] += w[i][j];
    }
  }
  return dp;
}

}  // namespace emthrm

#endif  // EMTHRM_DYNAMIC_PROGRAMMING_KNUTH_YAO_SPEEDUP_HPP_
#line 1 "include/emthrm/dynamic_programming/knuth_yao_speedup.hpp"



#include <algorithm>
#include <vector>

namespace emthrm {

template <typename T>
std::vector<std::vector<T>> knuth_yao_speedup(
    const std::vector<std::vector<T>>& w, const T inf) {
  const int n = w.size();
  std::vector<std::vector<T>> dp(n, std::vector<T>(n, inf));
  if (n == 0) [[unlikely]] return dp;
  std::vector<std::vector<int>> argmin(n, std::vector<int>(n, -1));
  for (int j = 0; j < n; ++j) {
    dp[j][j] = 0;
    argmin[j][j] = j;
    for (int i = j - 1; i >= 0; --i) {
      const int right = std::min(j - 1, argmin[i + 1][j]);
      for (int k = argmin[i][j - 1]; k <= right; ++k) {
        const T tmp = dp[i][k] + dp[k + 1][j];
        if (tmp < dp[i][j]) {
          dp[i][j] = tmp;
          argmin[i][j] = k;
        }
      }
      dp[i][j] += w[i][j];
    }
  }
  return dp;
}

}  // namespace emthrm
Back to top page