monotone minima (src/Optimization/monotone_minima.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2023-08-17 22:34:53+09:00
• Include: #include "src/Optimization/monotone_minima.hpp"

関数

名前	概要	計算量
monotone_minima(H,W,select)	monotone な $H\times W$ 行列に対して実行. 行列は陽には与えずselect関数を渡す. select(i,j,k) は $(i,j)$ -成分より $(i,k)$ -成分の方が望ましいなら true を返すという関数. ただし，呼ばれるときは必ず $j\lt k$． 返り値は各行 $i$ に対して最適解を達成する列方向 $j$ を返す.	$O((H+W)\log H)$

参考

https://topcoder-g-hatena-ne-jp.jag-icpc.org/spaghetti_source/20120923/1348327542.html

Verify

• COLOCON -Colopl programming contest 2018- Final C - スペースエクスプローラー高橋君
• 技術室奥プログラミングコンテスト#2 F - NPCの家 (NPC’s House)
• COLOCON -Colopl programming contest 2018- D - すぬけそだて――トレーニング――

Verified with

• test/aoj/2603.monotone_minima.test.cpp
• test/yosupo/min_plus_convolution_convex_arbitrary.monotone_minima.test.cpp
• test/yukicoder/913.monotone_minima.test.cpp
• test/yukicoder/952.monotone_minima.test.cpp

Code

#pragma once
#include <vector>
// select(i,j,k) -> true if (i,k) is better than (i,j)
template <typename F> std::vector<int> monotone_minima(int H, int W, const F &select) {
 std::vector<int> ret(H);
 auto rec= [&](auto &rec, int h1, int h2, int w1, int w2) -> void {
  if (h1 == h2) return;
  int h= (h1 + h2) / 2, best_w= w1;
  for (int w= w1 + 1; w < w2; ++w)
   if (select(h, best_w, w)) best_w= w;
  ret[h]= best_w, rec(rec, h1, h, w1, best_w + 1), rec(rec, h + 1, h2, best_w, w2);
 };
 return rec(rec, 0, H, 0, W), ret;
}

#line 2 "src/Optimization/monotone_minima.hpp"
#include <vector>
// select(i,j,k) -> true if (i,k) is better than (i,j)
template <typename F> std::vector<int> monotone_minima(int H, int W, const F &select) {
 std::vector<int> ret(H);
 auto rec= [&](auto &rec, int h1, int h2, int w1, int w2) -> void {
  if (h1 == h2) return;
  int h= (h1 + h2) / 2, best_w= w1;
  for (int w= w1 + 1; w < w2; ++w)
   if (select(h, best_w, w)) best_w= w;
  ret[h]= best_w, rec(rec, h1, h, w1, best_w + 1), rec(rec, h + 1, h2, best_w, w2);
 };
 return rec(rec, 0, H, 0, W), ret;
}

Back to top page