2022-03-13

周期関数の極小点を求めるアルゴリズム

定義

$f: \mathbb{Z} \to \mathbb{R}, ~ p \in \mathbb{Z} _ {\gt 0}$ が $\forall x. ~ f(n) = f(n + p)$ を満たすとする。 $n$ を与えると $f(n)$ を $\mathrm{O} (1)$ の時間計算量で取得できるとして、 $f(n - 1) \geq f(n), ~ f(n) \leq f(n + 1)$ を満たす $n$ を $\Theta(\log ( p ) )$ の時間計算量で求めるアルゴリズムが存在する。

アルゴリズム

一般の数列を三分探索すると極小点が求まるとは限らない - noshi91のメモ

上記の記事の後半で紹介しているアルゴリズムを、 $(l, m, r) := (0, p, 2p)$ で初期化して、 $f$ に対して適用すればよい。

実用例

$2$ 次元平面上に点群があり、ベクトル $v$ の方向に最も遠い点を求めることを考える。点群の凸包を $P$ 、その頂点を順に $a _ 1, a _ 2, \dots$ として $f(n) := v \cdot a _ n$ と定義する。 $f$ は $P$ の頂点数を周期とする関数であり、 $f$ の極大点が求める点である。

2022-03-13

一般の数列を三分探索すると極小点が求まるとは限らない

アルゴリズム

概要

三分探索を行うと極小点が $1$ つも求まらないような数列を構成した。また、一般の数列に対して $\Theta(\log (N))$ の時間計算量で極小点を $1$ つ求めるアルゴリズムを説明する。

定義

$A = (A _ 1, A _ 2, \dots, A _ N) ~ (N \geq 1)$ を実数列とする。整数 $i ~ (1 \leq i \leq N)$ が $A$ の極小点であることを、 $A _ {i - 1} \geq A _ {i}, ~ A _ {i} \leq A _ {i + 1}$ を満たすことと定義する。ただし仮想的に $A _ 0 = A _ {N + 1} = + \infty$ とする。

三分探索

$A$ が丁度 $1$ つの極小点を持つとき、三分探索を用いると $A$ に $\Theta(\log (N))$ 回アクセスすることでその極小点を求めることができる。三分探索は以下のようなアルゴリズムである。

最初、 $(l, r) := (0, N + 1)$ とする。「 $A$ の極小点 $i$ が $l \lt i \lt r$ を満たす」という条件を維持したまま $r - l$ を狭めていく。

$\textrm{(i)}$ $r - l = 2$ の場合

$(l + r) / 2$ が極小点であり、アルゴリズムを終了する。
$\textrm{(ii)}$ $r - l \geq 3$ の場合

$(l', r') := (\lfloor (2l + r) / 3 \rfloor, \lfloor (l + 2r) / 3 \rfloor )$ とする。 $(l, (2l + r) / 3, (l + 2r) / 3, r)$ は隣接項の差が $1$ 以上であるから、それぞれに floor 関数を適用した $(l, l', r', r)$ は狭義単調増加列になることに注意。
- $\textrm{(ii - i)}$ $A _ {l'} \lt A _ {r'}$ の場合
  
  $(l, r) \leftarrow (l, r')$ と更新して繰り返す。
- $\textrm{(ii - ii)}$ $A _ {l'} \gt A _ {r'}$ の場合
  
  $(l, r) \leftarrow (l', r)$ と更新して繰り返す。

$\textrm{(ii)}$ が起こるたびに $r - l$ は $\lceil 2(r - l) / 3 \rceil$ 以下になるから、時間計算量は $\mathrm{O}(\log (N))$ である。

三分探索で極小点が求まらないような一般の数列

$N = 26$ の例を図示した。数列ではなく関数のグラフになっているが、適当に離散化して考えて欲しい。

f:id:noshi91:20220313203519j:plain

$3$ 回のイテレーションの後 $(l, r) = (9, 17)$ となり、極小点が存在しないことが分かる。

一般の数列に対して、極小点を $1$ つ求めるアルゴリズム

黄金分割探索は、一般の数列に対しても $1$ つ極小点を求めることができる (詳細略)。本記事では、黄金分割探索とは異なるアルゴリズムを説明する。

最初 $(l, m, r) := (0, \lceil N / 2 \rceil, N + 1)$ とする *1。「 $l \lt m \lt r$ かつ $A _ l \geq A _ m, ~ A _ m \leq A _ r$ 」を満たすという条件を保ちつつ、 $r - l$ を狭めていく。

$\textrm{(i)}$ $r - l = 2$ の場合

$l + 1 = m = r - 1$ であり、不変条件から $m$ が極小点である。アルゴリズムを終了する。
$\textrm{(ii)}$ $r - l \geq 3$ の場合

$(l ^ {\prime}, r ^ {\prime}) := (\lfloor (l + m) / 2 \rfloor, \lceil (m + r) / 2 \rceil)$ とする。 $l \leq l' \lt m \lt r' \leq r$ である。
- $\textrm{(ii - i)}$ $A _ {l'} \lt A _ m$ の場合
  
  不変条件と併せて $A _ l \geq A _ m \gt A _ {l'}$ である。特に $A _ l \neq A _ {l'}$ より $l \lt l'$ も満たされるため、 $(l, m, r) \leftarrow (l, l', m)$ と更新して繰り返す。
- $\textrm{(ii - ii)}$ $A _ {m} \gt A _ {r'}$ の場合
  
  $\textrm{(ii - i)}$ の場合と対称である。 $(l, m, r) \leftarrow (m, r', r)$ と更新して繰り返す。
- $\textrm{(ii - iii)}$ $A _ {l'} \geq A _ m, ~ A _ m \leq A _ {r'}$ の場合
  
  $(l, m, r) \leftarrow (l', m, r')$ と更新して繰り返す。

$w := \max (m - l, r - m)$ と定義すると、 $\textrm{(ii)}$ が起こるたびに $w$ は $\lceil w / 2 \rceil$ 以下になるから、時間計算量は $\mathrm{O}(\log (N))$ である。

*1:実は $m = 1$ としてもほとんど問題ないが、イメージのしやすさのため $m$ は中央付近に取った

2022-01-13

Aliens DP で辺の本数が区間で指定される場合

アルゴリズム

概要

https://dic.kimiyuki.net/d-edge-shortest-path-monge

この記事においてラグランジュ双対などで説明した部分を凸共役の観点から解釈し、「 $a$ 本以上 $b$ 本以下使う最短路」も同じように解くことができることを解説します。

本文

合成積

関数 $f _ 1, f _ 2: \mathbb{R} \to \mathbb{R} \cup \lbrace + \infty \rbrace$ の合成積 $f _ 1 \square f _ 2$ は \begin{align} (f _ 1 \square f _ 2)(x) &= \inf _ {x _ 1 + x _ 2 = x} (f _ 1(x _ 1) + f _ 2(x _ 2)) \end{align} で定義されます。 $f _ 1, f _ 2$ が凸で $f _ 1 \square f _ 2$ が $- \infty$ にならなければ、 $f _ 1 \square f _ 2$ は凸です。

凸共役関数

関数 $f: \mathbb{R} \to \mathbb{R} \cup \lbrace + \infty \rbrace, ~ ~ \exists x. ~ f(x) \neq + \infty$ に対して、その凸共役関数 $f ^\bullet: \mathbb{R} \mapsto \mathbb{R} \cup \lbrace +\infty \rbrace$ を \begin{align} f ^\bullet (p) &= \sup _ x (px - f(x)) \end{align} で定義します。本記事では $\displaystyle f ^ \bullet (p) = - \min _ x (f(x) - px)$ と思っても差し支えありません。凸共役関数は本来もっと広いクラスの関数に対して定義されますが、本記事ではこれで十分です。

凸共役関数に対していくつかの良い性質が成り立ちます。

$f ^ \bullet$ は凸関数
$f$ が凸で特定の条件を満たすと $f ^ {\bullet \bullet} = f$
$f _ 1, f _ 2$ が凸で特定の条件を満たすと $(f _ 1 \square f _ 2) ^ \bullet = f _ 1 ^ \bullet + f _ 2 ^ \bullet$

これらの条件は少し複雑なので、本記事では特に確認せずに使用します。 [1] などを確認してください。

問題の整理

$f(x)$ を、辺を $x$ 本使うという条件下での最短距離と定義します。すると、

$f$ は凸
任意の $p$ に対し、 $\displaystyle \min _ x (f(x) - px) = - f ^ \bullet (p)$ が高速に評価できる
$f(d)$ を求めよ

という問題であると整理できます。

$f(d)$ の求め方

\begin{align} f(d) &= f ^ {\bullet \bullet} (d) \cr &= - \min _ {p} (f ^ \bullet (p) - dp) \cr \end{align}

$f ^ \bullet$ は凸なので $p \mapsto f ^ \bullet (p) - dp$ も凸であり、その最小化は三分探索で行えます。 $f ^ \bullet (p)$ が高速に評価できるので、目的が達成されました。

$\displaystyle \min _ {a \leq x \leq b} f(x)$ の求め方

$\delta _ {\lbrack a , b \rbrack}: \mathbb{R} \to \mathbb{R} \cup \lbrace +\infty \rbrace$ を \begin{align} \delta _ {\lbrack a , b \rbrack} (x) &= \begin{cases} 0 & \quad (a \leq x \leq b) \cr +\infty & \quad (\text{otherwise}) \end{cases} \end{align} で定義します。このとき \begin{align} \min _ {a \leq x \leq b} f(x) &= (f \square \delta _ {\lbrack -b , -a \rbrack}) (0) \cr &= (f \square \delta _ {\lbrack -b , -a \rbrack}) ^ {\bullet \bullet} (0) \cr &= - \min _ {p} ((f \square \delta _ {\lbrack -b , -a \rbrack}) ^ \bullet (p) - 0p) \cr &= - \min _ {p} (f ^ \bullet + {\delta _ {\lbrack -b , -a \rbrack}} ^ \bullet) (p) \end{align} $f ^ \bullet, \delta _ {\lbrack -b , -a \rbrack} ^ \bullet$ は凸関数なのでその和も凸であり、その最小化は三分探索で行えます。 ${\delta _ {\lbrack -b , -a \rbrack}} ^ \bullet$ は非常に単純な形になるので高速に評価でき、目的が達成されます。実際、 \begin{align} {\delta _ {\lbrack -b , -a \rbrack}} ^ \bullet (p) &= \begin{cases} -bp &\quad (p \leq 0) \cr -ap &\quad (p \geq 0) \end{cases} \end{align} です。

参考文献

[1] 室田一雄. (2001). 離散凸解析. 共立出版株式会社.

2022-01-02

Top Tree の構造の変種

データ構造

注意: 雑です

概要

[1] で定義された top tree は、葉が underlying tree の辺に対応するなどの条件があります。 [2] は splay tree をベースにした top tree を説明しています。 [1] の定義にはわずかに合致しないものの、いくらかの良い性質を持つ構造を思いついたので、本記事で説明します。

本文

link cut tree に類似した構造になっていて、根付き木を管理します。各辺は solid と dashed の 2 状態のいずれかであり、各頂点について子とをつなぐ辺の内 solid なものは高々 $1$ 本とするのも link cut tree と同様です。

link cut tree と異なるところは

solid edge からなるパスを管理する二分探索木
- link cut tree: $P$ を頂点の列と見て、 $P$ の頂点が $\mathcal{C}$ の頂点と $1$ 対 $1$ 対応する。
- 提案手法: $P$ を頂点と辺の列と見て、 $P$ の頂点が $\mathcal{C}$ の葉に、 $P$ の辺が $\mathcal{C}$ の内部ノードに $1$ 対 $1$ 対応する。
頂点に連なる dashed edge の管理
- link cut tree: それぞれの dashed edge から $v$ (に対応する $\mathcal{C}$ の頂点) へポインタを張る。
- 提案手法: 二分探索木 $\mathcal{R}$ で dashed edge を管理する。各 dashed edge と $\mathcal{R}$ の頂点が $1$ 対 $1$ 対応する。 $\mathcal{R}$ の頂点は middle child として dashed edge の先の部分木を管理する木構造の根へポインタを張る。

具体例です。

f:id:noshi91:20220102003524j:plain

図 1: 管理したい根付き木(左)と対応する link cut tree の例(右)。頂点の数字は元の木の頂点と対応している。

f:id:noshi91:20220102003753j:plain

図 2: 管理したい根付き木(左)と対応する提案手法の木の例(右)。丸いノードは元の木の頂点と、四角いノードは元の木の辺と対応している。

管理したい根付き木を $T = (V, E)$ とすれば、データ構造の全ての頂点が $V \amalg E$ と完全に $1$ 対 $1$ 対応します。また、提案した構造でも link cut tree と同様に splay や expose を行えば時間計算量が $\text{amortized} ~ \mathrm{O}(\log(N))$ になることも証明したつもりになっています (少し自信がありません)。

参考文献

[1] Alstrup, S., Holm, J., Lichtenberg, K. D., & Thorup, M. (2005). Maintaining information in fully dynamic trees with top trees. Acm Transactions on Algorithms (talg), 1(2), 243-264.

[2] Tarjan, R. E., & Werneck, R. F. F. (2005, January). Self-adjusting top trees. In SODA (Vol. 5, pp. 813-822).

2021-12-15

容量下限などが付いている最小費用流

アルゴリズム

概要

辺の流量に下限があったりする最小費用流を、思いつく範囲で一般化してみました。

記法の定義

$G = (V, E)$ を有向グラフとします。フロー $\xi \in \mathbb{Z} ^ E$ に対して、その境界 $\partial \xi \in \mathbb{Z} ^ V$ を $\displaystyle \partial \xi _ v = \sum _ {(v, u) \in E} \xi _ u - \sum _ {(u, v) \in E} \xi _ u$ で定義します。つまり、境界は各頂点から流れ出る量を表しています。

ベクトルに対して不等号を使ったときは、全ての成分について同時にその不等号が成り立つものと解釈します。例: $0 \leq c \Leftrightarrow c$ は非負ベクトル

$\lVert \cdot \rVert _ 1$ は $L ^ 1$ ノルムで、成分毎の絶対値の和です。

基本的な最小費用流

枝コスト $\gamma \in \mathbb{Z} _ {\geq 0} ^ {E}$
容量上限 $\overline{c} \in \mathbb{Z} ^ {E}$
source $s \in V$
sink $t \in V$
流量 $f \in \mathbb{Z} _ {\geq 0}$
$s \neq t$

\begin{align} \text{Minimize}&\quad \gamma ^ {\top} \xi \cr \text{subject to}&\quad 0 \leq \xi \leq \overline{c} \cr &\quad \partial \xi _ v = \begin{cases} f &\quad (v = s) \cr -f &\quad (v = t) \cr 0 &\quad (\text{otherwise}) \end{cases} \end{align}

$0 \leq \overline{c}$ の場合 ACL を使うとそのまま解くことができます。 $0 \leq \overline{c}$ でない場合は解がありません。時間計算量は $\mathrm{O}(f (\lvert V \rvert + \lvert E \rvert) \log (\lvert V \rvert + \lvert E \rvert))$ です。

b-flow

枝コスト $\gamma \in \mathbb{Z} _ {\geq 0} ^ {E}$
容量上限 $\overline{c} \in \mathbb{Z} ^ {E}$
供給 $x \in \mathbb{Z} ^ {V}$

\begin{align} \text{Minimize}&\quad \gamma ^ {\top} \xi \cr \text{subject to}&\quad 0 \leq \xi \leq \overline{c} \cr &\quad \partial \xi = x \end{align}

$\displaystyle \sum _ {x _ v \gt 0} x _ v = - \sum _ {x _ v \lt 0} x _ v$ が成り立っていないときは解がありません。そうでないとき

超頂点 $s, t$ を作成する
$x _ v \gt 0$ である $v$ に対して、 $s$ から $v$ に容量上限 $x _ v$ コスト $0$ の辺を張る
$x _ v \lt 0$ である $v$ に対して、 $v$ から $t$ に容量上限 $- x _ v$ コスト $0$ の辺を張る
$s$ から $t$ に $\lVert x \rVert _ 1 / 2$ 流す

で前述の問題に帰着されます。時間計算量は $\mathrm{O}(\lVert x \rVert _ 1 (\lvert V \rvert + \lvert E \rvert) \log (\lvert V \rvert + \lvert E \rvert) )$ です。

容量下限付き

枝コスト $\gamma \in \mathbb{Z} _ {\geq 0} ^ {E}$
容量下限 $\underline{c} \in \mathbb{Z} ^ {E}$
容量上限 $\overline{c} \in \mathbb{Z} ^ {E}$
供給 $x \in \mathbb{Z} ^ {V}$

\begin{align} \text{Minimize}&\quad \gamma ^ {\top} \xi \cr \text{subject to}&\quad \underline{c} \leq \xi \leq \overline{c} \cr &\quad \partial \xi = x \end{align}

これは

\begin{align} \text{Minimize}&\quad \gamma ^ {\top} (\xi - \underline{c}) + \gamma ^ {\top} \underline{c} \cr \text{subject to}&\quad 0 \leq \xi - \underline{c} \leq \overline{c} - \underline{c} \cr &\quad \partial (\xi - \underline{c}) = x - \partial \underline{c} \end{align}

と書き換えることができます。したがって $\xi - \underline{c}$ をフローと思うことで前述の問題に帰着されます。時間計算量は $\mathrm{O}(\lVert x - \partial \underline{c} \rVert _ 1 (\lvert V \rvert + \lvert E \rvert) \log (\lvert V \rvert + \lvert E \rvert)) \subseteq \mathrm{O}( (\lVert x \rVert _ 1 + \lVert \underline{c} \rVert _ 1) (\lvert V \rvert + \lvert E \rvert) \log (\lvert V \rvert + \lvert E \rvert) )$ です。

枝コストが負

枝コスト $\gamma \in \mathbb{Z} ^ {E}$
容量下限 $\underline{c} \in \mathbb{Z} ^ {E}$
容量上限 $\overline{c} \in \mathbb{Z} ^ {E}$
供給 $x \in \mathbb{Z} ^ {V}$

\begin{align} \text{Minimize}&\quad \gamma ^ {\top} \xi \cr \text{subject to}&\quad \underline{c} \leq \xi \leq \overline{c} \cr &\quad \partial \xi = x \end{align}

$\gamma _ a \lt 0$ である全ての $a \in E$ について、

$a$ の向きを逆にする
$\gamma _ a \leftarrow - \gamma _ a$
$(\underline{c} _ a, \overline{c} _ a) \leftarrow (-\overline{c} _ a, -\underline{c} _ a)$

とすると、前述の問題に帰着されます。時間計算量はコストが負の辺の容量上限で変わるので、適宜計算してください。

供給が区間、境界に線形のコスト

枝コスト $\gamma \in \mathbb{Z} ^ {E}$
容量下限 $\underline{c} \in \mathbb{Z} ^ {E}$
容量上限 $\overline{c} \in \mathbb{Z} ^ {E}$
境界コスト $\zeta \in \mathbb{Z} ^ V$
供給下限 $\underline{x} \in \mathbb{Z} ^ {V}$
供給上限 $\overline{x} \in \mathbb{Z} ^ {V}$

\begin{align} \text{Minimize}&\quad \gamma ^ {\top} \xi + \zeta ^ {\top} \partial \xi \cr \text{subject to}&\quad \underline{c} \leq \xi \leq \overline{c} \cr &\quad \underline{x} \leq \partial \xi \leq \overline{x} \end{align}

超頂点 $s$ を作成する
各 $v \in V$ について、 $s$ から $v$ に容量下限 $\underline{x} _ v$ 容量上限 $\overline{x} _ v$ コスト $\zeta _ v$ の辺を張る
供給 $x = 0$ として前述の問題に帰着

その他

$\mathbb{Z}$ の場合で議論しましたが、コストが $\mathbb{R}$ の場合や、 $\pm \infty$ が含まれる場合も概ね同様に議論できます。ただし容量下限付きを下限 $0$ に帰着するときに下限 $\underline{c}$ に $- \infty$ が含まれていると壊れます。これは容量上限 $+ \infty$ でコストが負の辺に対して「あらかじめ限界まで流しておく」が使えないことと同じです。

流量 $f$ が指定されず自由な量流していい最小費用流は、供給が区間の場合を使えば定式化できます。

2021-07-10

カタラン数を鏡像法で理解する

概要

この記事の内容は [1] の解説の一部を抜き出して説明したものです。カタラン数 $C(N)$ が $\displaystyle \binom{2N}{N} - \binom{2N}{N - 1}$ と等しいことを、鏡像法 *1 で説明します。

本文

$C(N)$ は、グリッド上を右上方向に、 $(0, 0)$ から $(N, N)$ まで、 $x \geq y$ を満たすように移動する方法の数と一致します。

f:id:noshi91:20210710163922j:plain

$x \geq y$ の条件を一旦忘れて、 $(0, 0)$ から $(N, N)$ までの経路の本数を数えることを考えます。これは以下のような動的計画法で計算できます。

\begin{align} \mathrm{dp}(i, j) = \begin{cases} 1 &\quad ( (i, j) = (0, 0) ) \cr \mathrm{dp}(i - 1, j) + \mathrm{dp}(i, j - 1) &\quad (\mathrm{otherwise}) \end{cases} \end{align}

f:id:noshi91:20210710164327j:plain

$x \geq y$ を、 $x + 1 = y$ を通らない、と言い換えます。するとカタラン数は、先ほどの例において $x + 1 = y$ 上で $\mathrm{dp} = 0$ にするような動的計画法で計算できます。

\begin{align} \mathrm{dp}(i, j) = \begin{cases} 1 &\quad ( (i, j) = (0, 0) ) \cr 0 &\quad ( i + 1 = j ) \cr \mathrm{dp}(i - 1, j) + \mathrm{dp}(i, j - 1) &\quad (\mathrm{otherwise}) \end{cases} \end{align}

f:id:noshi91:20210710164812j:plain

この $x + 1 = y$ 上で $\mathrm{dp} = 0$ にする操作を陽に行わずに表現する方法として、 $x + 1 = y$ に対して $(0, 0)$ と対称な位置に $-1$ の重みをもつスタート地点を置くという方法があります。

\begin{align} \mathrm{dp}(i, j) = \begin{cases} 1 &\quad ( (i, j) = (0, 0) ) \cr -1 &\quad ( (i, j) = (-1, 1) ) \cr \mathrm{dp}(i - 1, j) + \mathrm{dp}(i, j - 1) &\quad (\mathrm{otherwise}) \end{cases} \end{align}

f:id:noshi91:20210710170014j:plain

対称性から、対称軸上では $\mathrm{dp} = 0$ となることが分かるので、普通の経路数の動的計画法の更新式で、上手くカタラン数が求まっています。一方で $(0, 0)$ を始点とする経路の数と $(-1, 1)$ を始点とする経路の数は独立ですから、単に足し合わせれば

\begin{align} \text{カタラン数} &= \lbrace (0, 0) \text{から} (N, N) \text{への経路の数} \rbrace + (-1) \cdot \lbrace (-1, 1) \text{から} (N, N) \text{への経路の数} \rbrace \cr C(N) &= \binom{2N}{N} - \binom{2N}{N-1} \end{align}

が従います。

参考文献

[1]
ネタバレ注意
yukicoder 1241 Eternal Tours

*1:鏡像法は物理学の用語のようですが、発想が非常に似ているので、名前を借りています。

2021-06-29

最小カット問題の k 値への一般化

アルゴリズム

概要

最小カットを用いると、 $\alpha \in \mathbb{R},\ \theta _ i : \lbrace 0, 1 \rbrace \to \mathbb{R}$ 及び劣モジュラな $\phi _ {i, j} : \lbrace 0, 1 \rbrace ^ 2 \to \mathbb{R}$ について

\begin{align} \text{Minimize}&\quad \alpha + \sum _ i \theta _ i (x _ i) + \sum _ {i \lt j} \phi _ {i, j}(x _ i, x _ j) \cr \text{subject to}&\quad x \in \lbrace 0, 1 \rbrace ^ n \end{align}

という問題が解けます。[2]

これを一般化して、 $\alpha \in \mathbb{R},\ \theta _ i : k \to \mathbb{R}$ 及び Monge な $\phi _ {i, j} : k ^ 2 \to \mathbb{R}$ について

\begin{align} \text{Minimize}&\quad \alpha + \sum _ i \theta _ i (x _ i) + \sum _ {i \lt j} \phi _ {i, j}(x _ i, x _ j) \cr \text{subject to}&\quad x \in k ^ n \end{align}

は最小カットを用いて解けます。

本記事は [1] の内容を定式化し、表現可能な条件を明示的に記述します。

グラフの作り方

各変数 $x _ i$ に対して、 $\lbrace 0, 1 \rbrace$ の値を取る $k - 1$ 個の変数 $\lbrace x _ i ^ d \rbrace _ {d = 1} ^ {k - 1}$ を作ります。さらに、 $x _ i ^ d = 1 \land x _ i ^ {d + 1} = 0$ の場合 $+ \infty$ のコストが掛かることにします。これにより $\lbrace x _ i ^ d \rbrace _ {d = 1} ^ {k - 1}$ は丁度 $k$ 種類の状態を取るようになり、 $x _ i ^ d = 1 \leftrightarrow x _ i \lt d$ と対応させられます。

$\theta _ i : k \to \mathbb{R}$ が表現可能なことを示します。 $x _ i ^ d$ に対する $1$ 変数関数は常に表現可能であったことを思い出し、 $x _ i ^ d = 1$ のとき $\theta _ i (d - 1) - \theta _ i (d)$ のコストを掛けます。さらに無条件で $\theta _ i (k - 1)$ のコストを掛けると、 $\theta _ i$ が表現されます。

下図は上述の方法で表現した後、さらにグラフでの表現に直したものです。

f:id:noshi91:20210629043614j:plain

$\phi _ {i, j} : k ^ 2 \to \mathbb{R}$ が Monge ならば表現可能なことを示します。 $\alpha$ と $\theta _ i, \theta _ j$ を使うことで、 $\phi _ {i, j} (0, d) = \phi _ {i, j} (d, 0) = 0 \ (\forall \ d)$ としてよいです。 $x _ i ^ d = x _ j ^ e = 0$ のとき $\phi _ {i, j} (d, e) - \phi _ {i, j} (d, e - 1) - \phi _ {i, j} (d - 1, e) + \phi _ {i, j} (d - 1, e - 1)$ のコストを掛けます。 $\phi _ {i, j}$ の Monge 性から、このコストは劣モジュラです。

yukicoder No.119 旅行ツアーの問題

この節は [3] の内容を前節の内容を通して捉え直します。

各国 $i$ について $0:$ 国に行かない, $1:$ 国には行くがツアーに行かない, $2:$ ツアーに行く, の $3$ つの選択肢を選ぶ問題であり、 $k = 3$ とした場合の前節の問題の枠組みで解釈できます。 $B _ i, C _ i$ に関係する部分は $1$ 変数関数になるため、常に表現可能です ( $B _ i, C _ i$ が負であっても)。 $2$ 変数が関係する部分は、「国 $i$ のツアーに行き国 $j$ に行くならば、国 $j$ のツアーに行かなければならない」です。これを図示すると以下のようなコストになります。

f:id:noshi91:20210629043658j:plain

このままでは Monge でないので、 $0, 1, 2$ を $1, 0, 2$ の順に並び替えます。すると以下のようになります。

f:id:noshi91:20210629043940j:plain

これは Monge なので、最小カットで解くことができます。 $k = 2$ の場合 $0, 1$ を全ての変数で一斉に入れ替えても劣モジュラ性は変化しませんでしたが、 $k \geq 3$ の場合は Monge 性に影響を与えるということになります。

問題例

	出題場所	コンテスト名	問題名
0	KUPC	KUPC2019	123パズル
1	ARC	ARC 107	Sum of Abs

その他

グラフの作り方から明らかなように、 $k$ の値は変数ごとに異なっても構いません。

参考文献

[1] tokoharu-sakura. (2017). Project Selection (燃やす埋める) 周りの話についてもう少し考えた. とこはるのまとめ. https://tokoharuland.hateblo.jp/entry/2017/12/25/000003
[2] つる. (2020). 燃やす埋める問題と劣モジュラ関数のグラフ表現可能性その①. 私と理論. https://theory-and-me.hatenablog.com/entry/2020/03/13/180935
[3] ねぼこ. (2021). yukicoder No.119 旅行のツアーの問題解説. neboccoのブログ. https://nebocco.hatenablog.com/entry/2021/03/18/200000

定義

実用例

概要

定義

三分探索

三分探索で極小点が求まらないような一般の数列

一般の数列に対して、極小点を つ求めるアルゴリズム

概要

本文

合成積

凸共役関数

問題の整理

の求め方

の求め方

参考文献

注意: 雑です

概要

本文

参考文献

概要

記法の定義

基本的な最小費用流

b-flow

容量下限付き

枝コストが負

供給が区間、境界に線形のコスト

その他

概要

本文

参考文献

概要

グラフの作り方

yukicoder No.119 旅行ツアーの問題

問題例

その他

参考文献

一般の数列に対して、極小点を $1$ つ求めるアルゴリズム

$f(d)$ の求め方

$\displaystyle \min _ {a \leq x \leq b} f(x)$ の求め方