Share
Embed
Monge の手引書
totally monotone, monotone, monotone minima, Monge, SMAWK algorithm, LARSCH algorithm を 1 つのスライドにまとめました
tatyam
April 20, 2023
Transcript
272 slides
-
注意事項 証明はあんまりやりません。 証明を読みたい人は [Monge まとめ①] Monge 性とは? – HackMD Knuth-Yao
speedup – 週刊 spaghetti_source とかを読んでみてください 2 -
凸包の双対問題ってありますよね? 凸包の双対問題 本の直線 が与 えられる 各 での最小値 を 求めたい。 N
l , … , l 1 N x L(x) = min{l (x), … , l (x)} 1 N 3 -
凸包の双対問題 本の直線 が与 えられる 各 での最小値 を 求めたい。 N l
, … , l 1 N x L(x) = min{l (x), … , l (x)} 1 N 4 -
Andrew's monotone chain の双対 1. 直線を傾きでソートする 2. の順に以下を 行う i.
直線 を追加する i = 1, … , N l i 6 -
Andrew's monotone chain の双対 1. 直線を傾きでソートする 2. の順に以下を 行う i.
直線 を追加する i = 1, … , N l i 7 -
Andrew's monotone chain の双対 1. 直線を傾きでソートする 2. の順に以下を 行う i.
直線 を追加する i = 1, … , N l i 8 -
Andrew's monotone chain の双対 1. 直線を傾きでソートする 2. の順に以下を 行う i.
直線 を追加する i = 1, … , N l i 9 -
Andrew's monotone chain の双対 1. 直線を傾きでソートする 2. の順に以下を 行う i.
直線 を追加する ii. 「一つ前の直線が不要であ れば削除する」を繰り返す i = 1, … , N l i 10 -
Andrew's monotone chain の双対 1. 直線を傾きでソートする 2. の順に以下を 行う i.
直線 を追加する ii. 「一つ前の直線が不要であ れば削除する」を繰り返す i = 1, … , N l i 11 -
Andrew's monotone chain の双対 1. 直線を傾きでソートする 2. の順に以下を 行う i.
直線 を追加する ii. 「一つ前の直線が不要であ れば削除する」を繰り返す i = 1, … , N l i 12 -
Andrew's monotone chain の双対 1. 直線を傾きでソートする 2. の順に以下を 行う i.
直線 を追加する ii. 「一つ前の直線が不要であ れば削除する」を繰り返す i = 1, … , N l i 13 -
Andrew's monotone chain の双対 1. 直線を傾きでソートする 2. の順に以下を 行う i.
直線 を追加する ii. 「一つ前の直線が不要であ れば削除する」を繰り返す i = 1, … , N l i 14 -
Andrew's monotone chain の双対 1. 直線を傾きでソートする 2. の順に以下を 行う i.
直線 を追加する ii. 「一つ前の直線が不要であ れば削除する」を繰り返す i = 1, … , N l i 15 -
だから双対なんですね〜 Andrew's monotone chain 1. 点を 座標でソートする 2. の順に以下を行う i.
点 を追加する ii. 「一つ前の点が不要であれば削 除する」を繰り返す の双対 (CHT) 1. 直線を傾きでソートする 2. の順に以下を行う i. 直線 を追加する ii. 「一つ前の直線が不要であれば 削除する」を繰り返す → 本質的に同じアルゴリズム x i = 1, … , N p i i = 1, … , N l i 19 -
Andrew's monotone chain の双対 1. 曲線を無限に左に伸ばした ときの高さでソートする 2. の順に以 下を行う
i. 直線 を追加する ii. 「一つ前の直線が不 要であれば削除す る」を繰り返す (実演) i = 1, … , N l i 26 -
行列を作る 曲線群をいくつかの 座標で切 って、その位置での値で行列を作 ってみる x l 1 l
2 l 3 l 4 l 5 l 6 l 7 x 1 7 11 20 24 50 38 118 27 -
行列を作る l 1 l 2 l 3
l 4 l 5 l 6 l 7 x 1 7 11 20 24 50 38 118 x 2 23 13 17 16 36 18 62 28 -
行列を作る l 1 l 2 l 3
l 4 l 5 l 6 l 7 x 1 7 11 20 24 50 38 118 x 2 23 13 17 16 34 18 62 x 3 47 22 21 16 31 6 36 29 -
行列を作る l 1 l 2 l 3
l 4 l 5 l 6 l 7 x 1 7 11 20 24 50 38 118 x 2 23 13 17 16 36 18 62 x 3 47 22 21 16 31 6 34 x 4 75 42 37 25 34 4 7 30 -
こうしてできた行列は、曲線群のときの制約を保存している 行列の性質 任意の つの列を取り出すと、上か ら何行かの大小関係が 向きで、残 りの行の大小関係が 向き であ る。
2 < > l 1 l 2 l 3 l 4 l 5 l 6 l 7 x 1 7 11 20 24 50 38 118 x 2 23 13 17 16 36 18 62 x 3 47 22 21 16 31 6 34 x 4 75 42 37 25 34 4 7 31 -
行列の性質 任意の つの列を取り出すと、上から 何行かの大小関係が 向きで、残りの 行の大小関係が 向き である。 向きの後 向きになることはない
→ もしそうなったら、最初に曲線をソート したことに矛盾 2 < > > < 32 -
行列の性質 任意の つの列を取り出すと、上か ら何行かの大小関係が 向きで、残 りの行の大小関係が 向き であ る。 →
このような行列を totally monotone 行列と言う 2 < > l 1 l 2 l 3 l 4 l 5 l 6 l 7 x 1 7 11 20 24 50 38 118 x 2 23 13 17 16 36 18 62 x 3 47 22 21 16 31 6 34 x 4 75 42 37 25 34 4 7 33 -
totally monotone 行列 の実数の行列であって、任意の つの列を取り出すと、上から何行か の大小関係が 向きで、残りの行の大小関係が 向き であるようなもの。 totally
monotone が出てきたら、 つの曲線が高々 度しか交わらないよう な曲線群を思い出すと良い。 N × M 2 < > 2 1 34 -
monotone 行列 totally monotone より弱い の実数の行列であって、各 行の最小値を取る位置が、下の行に 行くにつれて右になるようなもの。 N ×
M l 1 l 2 l 3 l 4 l 5 l 6 l 7 x 1 7 11 20 24 50 38 118 x 2 23 13 17 16 36 18 62 x 3 47 22 21 16 31 6 34 x 4 75 42 37 25 34 4 7 35 -
totally monotone ならば monotone monotone でないと仮定すると… l 1 l
2 l 3 l 4 l 5 l 6 l 7 x 1 7 11 20 24 50 38 118 x 2 47 22 21 16 31 6 34 x 3 23 13 17 16 36 18 62 x 4 75 42 37 25 34 4 7 36 -
totally monotone ならば monotone monotone でないと仮定すると… 本の曲線を取り出せば… 大小関係が逆になっているので totally monotone
でない。 2 l 2 l 6 x 1 11 38 x 2 22 6 x 3 13 18 x 4 42 4 37 -
ところで monotone っていう名前が被る 線形代数における monotone matrix 線形代数とは分野が離れているので良いとして 集合関数における monotone (単調)
日本語で「単調」と言ったらこちらを指すことにします ∀v ∈ R : M Av ≥ 0 ⟹ v ≥ 0 X ⊂ Y ⟹ f(X) ≤ f(Y ) 38 -
曲線群の最小値を求める問題は以下のように変換された。 行最小値問題 実数からなる 行列 が与えられる。 の各行での最小値 (がどこにあるか) を求めよ。 つまり、 について以下を求めよ。
b[i] = A j=1,…,M arg min i,j 今日はこの問題を深掘りしてみましょう (注 : 行列は totally monotone とは限らない) N × M A A i = 1, … , N 39 -
workshop 各行での最小値 (がどこにあるか) を求めよ。 l 1 l 2
l 3 l 4 l 5 l 6 l 7 l 8 x 1 25 62 47 78 36 66 50 79 x 2 49 70 64 73 46 64 93 16 x 3 27 48 75 67 49 74 33 66 x 4 23 48 88 59 42 67 65 31 x 5 87 43 80 34 44 48 35 45 x 6 93 37 85 27 66 56 90 97 41 -
workshop 各行での最小値 (がどこにあるか) を求めよ。 答え : l 1 l
2 l 3 l 4 l 5 l 6 l 7 l 8 x 1 25 62 47 78 36 66 50 79 x 2 49 70 64 73 46 64 93 16 x 3 27 48 75 67 49 74 33 66 x 4 23 48 88 59 42 67 65 31 x 5 87 43 80 34 44 48 35 45 x 6 93 37 85 27 66 56 90 97 25, 16, 27, 23, 34, 27 42 -
行最小値問題 実数からなる 行列 が与えられる。 の各行での最小値 (がどこにあるか) を求めよ。 計算量は? 全部調べるしかない。 時間
N × M A A Θ(NM) 43 -
monotone の場合は? について以下を求めよ。 b[i] = A j=1,…,M arg
min i,j ただし、 である。 これならもう少し効率的に求められそう! i = 1, … , N b[1] ≤ b[2] ≤ ⋯ ≤ b[N] 44 -
workshop 各行での最小値 (がどこにあるか) を求めよ。ただし行列は monotone である。 l 1 l
2 l 3 l 4 l 5 l 6 l 7 l 8 l 9 l 10 x 1 82 13 45 14 99 41 53 99 25 26 x 2 13 40 12 65 25 84 20 82 84 18 x 3 89 36 22 49 47 81 35 95 68 72 x 4 50 68 73 68 32 59 35 64 99 76 x 5 82 51 99 48 28 36 99 75 79 32 x 6 55 97 57 71 37 81 91 83 91 41 x 7 44 24 67 89 41 91 11 76 78 61 46 -
workshop 各行での最小値 (がどこにあるか) を求めよ。ただし行列は monotone である。 答え : l
1 l 2 l 3 l 4 l 5 l 6 l 7 l 8 l 9 l 10 x 1 82 13 45 14 99 41 53 99 25 26 x 2 13 40 12 65 25 84 20 82 84 18 x 3 89 36 22 49 47 81 35 95 68 72 x 4 50 68 73 68 32 59 35 64 99 76 x 5 82 51 99 48 28 36 99 75 79 32 x 6 55 97 57 71 37 81 91 83 91 41 x 7 44 24 67 89 41 91 11 76 78 61 13, 12, 22, 32, 28, 37, 11 47 -
workshop コツは掴めましたか? monotone 行列の定義 b[1] ≤ b[2] ≤ ⋯ ≤
b[N] をうまく使いましょう。 48 -
monotone minima 1. 中央の行の最小値を見つける l 1 l 2
l 3 l 4 l 5 l 6 l 7 l 8 l 9 l 10 x 1 82 13 45 14 99 41 53 99 25 26 x 2 13 40 12 65 25 84 20 82 84 18 x 3 89 36 22 49 47 81 35 95 68 72 x 4 50 68 73 68 32 59 35 64 99 76 x 5 82 51 99 48 28 36 99 75 79 32 x 6 55 97 57 71 37 81 91 83 91 41 x 7 44 24 67 89 41 91 11 76 78 61 50 -
monotone minima 1. 中央の行の最小値を見つける l 1 l 2
l 3 l 4 l 5 l 6 l 7 l 8 l 9 l 10 x 4 50 68 73 68 32 59 35 64 99 76 51 -
monotone minima 1. 中央の行の最小値を見つける l 1 l 2
l 3 l 4 l 5 l 6 l 7 l 8 l 9 l 10 x 4 50 68 73 68 32 59 35 64 99 76 52 -
monotone minima 1. 中央の行の最小値を見つける l 1 l 2
l 3 l 4 l 5 l 6 l 7 l 8 l 9 l 10 x 1 82 13 45 14 99 41 53 99 25 26 x 2 13 40 12 65 25 84 20 82 84 18 x 3 89 36 22 49 47 81 35 95 68 72 x 4 50 68 73 68 32 59 35 64 99 76 x 5 82 51 99 48 28 36 99 75 79 32 x 6 55 97 57 71 37 81 91 83 91 41 x 7 44 24 67 89 41 91 11 76 78 61 53 -
ここで monotone 性を使います monotone minima 1. 中央の行の最小値を 見つける 2. 最小値にならない部
分を捨てる 長方形領域 つが残りました 2 l 1 l 2 l 3 l 4 l 5 l 6 l 7 l 8 l 9 l 10 x 1 82 13 45 14 99 41 53 99 25 26 x 2 13 40 12 65 25 84 20 82 84 18 x 3 89 36 22 49 47 81 35 95 68 72 x 4 50 68 73 68 32 59 35 64 99 76 x 5 82 51 99 48 28 36 99 75 79 32 x 6 55 97 57 71 37 81 91 83 91 41 x 7 44 24 67 89 41 91 11 76 78 61 54 -
monotone minima 1. 中央の行の最小値を見つける 2. 最小値にならない部分を捨てる 3. 残った 2 個の長方形について再帰的に解
く l 1 l 2 l 3 l 4 l 5 x 1 82 13 45 14 99 x 2 13 40 12 65 25 x 3 89 36 22 49 47 l 5 l 6 l 7 l 8 l 9 l 10 x 5 28 36 99 75 79 32 x 6 37 81 91 83 91 41 x 7 41 91 11 76 78 61 55 -
monotone minima 1. 中央の行の最小値を見つける 2. 最小値にならない部分を捨てる 3. 残った 2 個の長方形について再帰的に解
く l 1 l 2 l 3 l 4 l 5 x 1 82 13 45 14 99 x 2 13 40 12 65 25 x 3 89 36 22 49 47 l 5 l 6 l 7 l 8 l 9 l 10 x 5 28 36 99 75 79 32 x 6 37 81 91 83 91 41 x 7 41 91 11 76 78 61 56 -
monotone minima 1. 中央の行の最小値を見つける 2. 最小値にならない部分を捨てる 3. 残った 2 個の長方形について再帰的に解く
monotone 行列の行最小値が で求められる 定数倍が軽く、 系のアルゴリズム (SMAWK, LARSCH など) と 区別するのがやや難しい Θ(N + M log N) Θ(N + M) 57 -
monotone minima monotone 行列の行最小値が で求められる ところで 行列の入力に 掛かってしまうのでは? Θ(N +
M log N) Θ(NM) 58 -
行列の入力に 掛かってしまうのでは? → 行番号 と列番号 を与えると値を で計算してくれる関数 が与 えられると思うと良い。 例えば、
の計算に 時間掛かる場合は、計算量に が 掛かります。 Θ(NM) i j Θ(1) A(i, j) A(i, j) Θ(log N) Θ(log N) 59 -
もうひとつの解釈 1. 偶数行のみを取り出して再 帰的に解く l 1 l 2
l 3 l 4 l 5 l 6 l 7 l 8 l 9 l 10 x 1 82 13 45 14 99 41 53 99 25 26 x 2 13 40 12 65 25 84 20 82 84 18 x 3 89 36 22 49 47 81 35 95 68 72 x 4 50 68 73 68 32 59 35 64 99 76 x 5 82 51 99 48 28 36 99 75 79 32 x 6 55 97 57 71 37 81 91 83 91 41 x 7 44 24 67 89 41 91 11 76 78 61 61 -
もうひとつの解釈 1. 偶数行のみを取り出して再 帰的に解く l 1 l 2
l 3 l 4 l 5 l 6 l 7 l 8 l 9 l 10 x 2 13 40 12 65 25 84 20 82 84 18 x 4 50 68 73 68 32 59 35 64 99 76 x 6 55 97 57 71 37 81 91 83 91 41 62 -
もうひとつの解釈 1. 偶数行のみを取り出して再 帰的に解く 2. 残りの部分の最小値を求め る ( 回の比較を行 う)
M − 1 l 1 l 2 l 3 l 4 l 5 l 6 l 7 l 8 l 9 l 10 x 4 50 68 73 68 32 59 35 64 99 76 63 -
もうひとつの解釈 1. 偶数行のみを取り出して再 帰的に解く 2. 残りの部分の最小値を求め る ( 回の比較を行 う)
M − 1 l 1 l 2 l 3 l 4 l 5 l 6 l 7 l 8 l 9 l 10 x 4 50 68 73 68 32 59 35 64 99 76 64 -
もうひとつの解釈 1. 偶数行のみを取り出して再 帰的に解く l 1 l 2
l 3 l 4 l 5 l 6 l 7 l 8 l 9 l 10 x 2 13 40 12 65 25 84 20 82 84 18 x 4 50 68 73 68 32 59 35 64 99 76 x 6 55 97 57 71 37 81 91 83 91 41 65 -
もうひとつの解釈 1. 偶数行のみを取り出して再 帰的に解く 2. 最小値にならない部分を捨 てる l 1
l 2 l 3 l 4 l 5 l 6 l 7 l 8 l 9 l 10 x 2 13 40 12 65 25 84 20 82 84 18 x 4 50 68 73 68 32 59 35 64 99 76 x 6 55 97 57 71 37 81 91 83 91 41 66 -
もうひとつの解釈 1. 偶数行のみを取り出して再 帰的に解く 2. 最小値にならない部分を捨 てる 3. 残りの部分の最小値を求め る
( 回の比較を行 う) M − 1 l 1 l 2 l 3 l 4 l 5 l 6 l 7 l 8 l 9 l 10 x 2 13 40 12 65 25 84 20 82 84 18 x 4 50 68 73 68 32 59 35 64 99 76 x 6 55 97 57 71 37 81 91 83 91 41 67 -
もうひとつの解釈 1. 偶数行のみを取り出して再 帰的に解く 2. 最小値にならない部分を捨 てる 3. 残りの部分の最小値を求め る
( 回の比較を行 う) M − 1 l 1 l 2 l 3 l 4 l 5 l 6 l 7 l 8 l 9 l 10 x 2 13 40 12 65 25 84 20 82 84 18 x 4 50 68 73 68 32 59 35 64 99 76 x 6 55 97 57 71 37 81 91 83 91 41 68 -
もうひとつの解釈 1. 偶数行のみを取り出して再 帰的に解く l 1 l 2
l 3 l 4 l 5 l 6 l 7 l 8 l 9 l 10 x 1 82 13 45 14 99 41 53 99 25 26 x 2 13 40 12 65 25 84 20 82 84 18 x 3 89 36 22 49 47 81 35 95 68 72 x 4 50 68 73 68 32 59 35 64 99 76 x 5 82 51 99 48 28 36 99 75 79 32 x 6 55 97 57 71 37 81 91 83 91 41 x 7 44 24 67 89 41 91 11 76 78 61 69 -
もうひとつの解釈 1. 偶数行のみを取り出して再 帰的に解く 2. 最小値にならない部分を捨 てる l 1
l 2 l 3 l 4 l 5 l 6 l 7 l 8 l 9 l 10 x 1 82 13 45 14 99 41 53 99 25 26 x 2 13 40 12 65 25 84 20 82 84 18 x 3 89 36 22 49 47 81 35 95 68 72 x 4 50 68 73 68 32 59 35 64 99 76 x 5 82 51 99 48 28 36 99 75 79 32 x 6 55 97 57 71 37 81 91 83 91 41 x 7 44 24 67 89 41 91 11 76 78 61 70 -
もうひとつの解釈 1. 偶数行のみを取り出して再 帰的に解く 2. 最小値にならない部分を捨 てる 3. 残りの部分の最小値を求め る
( 回の比較を行 う) やっていることとしてはこちらの解釈でも同じですね M − 1 l 1 l 2 l 3 l 4 l 5 l 6 l 7 l 8 l 9 l 10 x 1 82 13 45 14 99 41 53 99 25 26 x 2 13 40 12 65 25 84 20 82 84 18 x 3 89 36 22 49 47 81 35 95 68 72 x 4 50 68 73 68 32 59 35 64 99 76 x 5 82 51 99 48 28 36 99 75 79 32 x 6 55 97 57 71 37 81 91 83 91 41 x 7 44 24 67 89 41 91 11 76 78 61 71 -
SMAWK algorithm totally monotone 行列の行最小値は で求められる。 Geometric applications of a
matrix-searching algorithm, Algorithmica volume 2, pp. 195–208 (1987) 論文の著者 Peter Shor Shlomo Moran Alok Aggarwal Robert Wilber Maria M. Klawe Θ(N + M) 73 -
monotone minima に一工夫加えると SMAWK algorithm になる monotone minima 1. 偶数行のみを取り出して再帰的に解く
2. 最小値にならない部分を捨てる 3. 残りの部分の最小値を求める ( 回の比較を行う) M − 1 74 -
monotone minima に一工夫加えると SMAWK algorithm になる SMAWK algorithm 1. "Reduce"
step : 最小値にならない列を捨てる 2. "Recurse" step : 偶数行のみを取り出して再帰的に解く 3. 最小値にならない部分を捨てる 4. "Interpolate" step : 残りの部分の最小値を求める ( 回の比較を行う) M − 1 75 -
"Reduce" step は何をしているかというと… SMAWK algorithm 1. "Reduce" step : 最小値になら
ない列を捨てる 2. "Recurse" step : 偶数行のみ を取り出して再帰的に解く 3. 最小値にならない部分を捨てる 4. "Interpolate" step : 残りの部 分の最小値を求める: "Reduce" step 入力 : の totally monotone 行 列 出力 : 最小値を取り得ない列 個 計算量 : 計算量は? Θ(N + M) N × M M − N Θ(M) 76 -
"Reduce" step 入力 : の totally monotone 行列 出力 :
最小値を取り得ない列 個 から始めて、以下を繰り返す。 マス とマス を比較する。 最小値が存在しないことが分かった列を捨てる。 捨てた場合は を減らし、捨てなかった場合は を増やす。 実際にやってみよう N × M M − N i = 1 (i, i) (i, i + 1) i i 78 -
totally monotone の復習 任意の つの列を取り出すと、上から 何行かの大小関係が 向きで、残りの 行の大小関係が 向き である。
を見つけたら上に伝播する を見つけたら下に伝播する 2 < > < > 79 -
"Reduce" step と を比較する。要らなくなった列は捨てる。
x 1 x 2 x 3 x 4 x 5 x 6 x 7 l 1 10 34 23 45 60 57 50 l 2 22 38 27 49 64 61 54 l 3 19 29 16 38 53 50 43 l 4 20 30 9 31 46 43 35 l 5 25 35 10 28 43 40 33 l 6 32 42 17 27 42 39 32 l 7 32 42 17 25 34 31 24 l 8 43 53 28 36 37 34 27 l 9 44 54 29 37 38 27 20 l 10 48 58 33 41 42 25 16 l 11 52 62 37 45 46 29 12 l 12 59 69 44 52 53 36 15 l 13 54 64 39 47 48 31 10 を見つけたので上に伝播、 が最小値でない以外は分からないので次の行に進む (i, i) (i, i + 1) < 22 80 -
"Reduce" step と を比較する。要らなくなった列は捨てる。
x 1 x 2 x 3 x 4 x 5 x 6 x 7 l 1 10 34 23 45 60 57 50 l 2 22 38 27 49 64 61 54 l 3 19 29 16 38 53 50 43 l 4 20 30 9 31 46 43 35 l 5 25 35 10 28 43 40 33 l 6 32 42 17 27 42 39 32 l 7 32 42 17 25 34 31 24 l 8 43 53 28 36 37 34 27 l 9 44 54 29 37 38 27 20 l 10 48 58 33 41 42 25 16 l 11 52 62 37 45 46 29 12 l 12 59 69 44 52 53 36 15 l 13 54 64 39 47 48 31 10 を見つけたので下に伝播、 の列はどれも最小値でないことが分かるので捨てることができる (!) (i, i) (i, i + 1) > l 2 81 -
"Reduce" step と を比較する。要らなくなった列は捨てる。
x 1 x 2 x 3 x 4 x 5 x 6 x 7 l 1 10 34 23 45 60 57 50 l 3 19 29 16 38 53 50 43 l 4 20 30 9 31 46 43 35 l 5 25 35 10 28 43 40 33 l 6 32 42 17 27 42 39 32 l 7 32 42 17 25 34 31 24 l 8 43 53 28 36 37 34 27 l 9 44 54 29 37 38 27 20 l10 48 58 33 41 42 25 16 l 11 52 62 37 45 46 29 12 l 12 59 69 44 52 53 36 15 l 13 54 64 39 47 48 31 10 捨てたので 行目の比較をやり直し。 なので上に伝播 (i, i) (i, i + 1) 1 < 82 -
"Reduce" step と を比較する。要らなくなった列は捨てる。
x 1 x 2 x 3 x 4 x 5 x 6 x 7 l 1 10 34 23 45 60 57 50 l 3 19 29 16 38 53 50 43 l4 20 30 9 31 46 43 35 l 5 25 35 10 28 43 40 33 l 6 32 42 17 27 42 39 32 l 7 32 42 17 25 34 31 24 l 8 43 53 28 36 37 34 27 l 9 44 54 29 37 38 27 20 l 10 48 58 33 41 42 25 16 l11 52 62 37 45 46 29 12 l 12 59 69 44 52 53 36 15 l 13 54 64 39 47 48 31 10 なので上に伝播 (i, i) (i, i + 1) < 83 -
"Reduce" step と を比較する。要らなくなった列は捨てる。
x 1 x 2 x 3 x 4 x 5 x 6 x 7 l 1 10 34 23 45 60 57 50 l 3 19 29 16 38 53 50 43 l4 20 30 9 31 46 43 35 l 5 25 35 10 28 43 40 33 l 6 32 42 17 27 42 39 32 l 7 32 42 17 25 34 31 24 l 8 43 53 28 36 37 34 27 l 9 44 54 29 37 38 27 20 l 10 48 58 33 41 42 25 16 l11 52 62 37 45 46 29 12 l 12 59 69 44 52 53 36 15 l 13 54 64 39 47 48 31 10 (i, i) (i, i + 1) 84 -
"Reduce" step と を比較する。要らなくなった列は捨てる。
x 1 x 2 x 3 x 4 x 5 x 6 x 7 l 1 10 34 23 45 60 57 50 l 3 19 29 16 38 53 50 43 l4 20 30 9 31 46 43 35 l 5 25 35 10 28 43 40 33 l 6 32 42 17 27 42 39 32 l 7 32 42 17 25 34 31 24 l 8 43 53 28 36 37 34 27 l 9 44 54 29 37 38 27 20 l 10 48 58 33 41 42 25 16 l11 52 62 37 45 46 29 12 l 12 59 69 44 52 53 36 15 l 13 54 64 39 47 48 31 10 を見つけたので下に伝播、 の列はどれも最小値でないことが分かるので捨てることができる (i, i) (i, i + 1) > l 5 85 -
"Reduce" step と を比較する。要らなくなった列は捨てる。
x 1 x 2 x 3 x 4 x 5 x 6 x 7 l 1 10 34 23 45 60 57 50 l 3 19 29 16 38 53 50 43 l 4 20 30 9 31 46 43 35 l 6 32 42 17 27 42 39 32 l 7 32 42 17 25 34 31 24 l 8 43 53 28 36 37 34 27 l 9 44 54 29 37 38 27 20 l 10 48 58 33 41 42 25 16 l 11 52 62 37 45 46 29 12 l 12 59 69 44 52 53 36 15 l 13 54 64 39 47 48 31 10 (i, i) (i, i + 1) 86 -
"Reduce" step と を比較する。要らなくなった列は捨てる。
x 1 x 2 x 3 x 4 x 5 x 6 x 7 l 1 10 34 23 45 60 57 50 l 3 19 29 16 38 53 50 43 l 4 20 30 9 31 46 43 35 l 6 32 42 17 27 42 39 32 l 7 32 42 17 25 34 31 24 l 8 43 53 28 36 37 34 27 l 9 44 54 29 37 38 27 20 l 10 48 58 33 41 42 25 16 l 11 52 62 37 45 46 29 12 l 12 59 69 44 52 53 36 15 l 13 54 64 39 47 48 31 10 (i, i) (i, i + 1) 87 -
"Reduce" step と を比較する。要らなくなった列は捨てる。
x 1 x 2 x 3 x 4 x 5 x 6 x 7 l 1 10 34 23 45 60 57 50 l3 19 29 16 38 53 50 43 l 4 20 30 9 31 46 43 35 l 7 32 42 17 25 34 31 24 l 8 43 53 28 36 37 34 27 l 9 44 54 29 37 38 27 20 l 10 48 58 33 41 42 25 16 l 11 52 62 37 45 46 29 12 l 12 59 69 44 52 53 36 15 l 13 54 64 39 47 48 31 10 (i, i) (i, i + 1) 88 -
"Reduce" step と を比較する。要らなくなった列は捨てる。
x 1 x 2 x 3 x 4 x 5 x 6 x 7 l 1 10 34 23 45 60 57 50 l3 19 29 16 38 53 50 43 l 4 20 30 9 31 46 43 35 l 7 32 42 17 25 34 31 24 l 8 43 53 28 36 37 34 27 l 9 44 54 29 37 38 27 20 l 10 48 58 33 41 42 25 16 l 11 52 62 37 45 46 29 12 l 12 59 69 44 52 53 36 15 l 13 54 64 39 47 48 31 10 (i, i) (i, i + 1) 89 -
"Reduce" step と を比較する。要らなくなった列は捨てる。
x 1 x 2 x 3 x 4 x 5 x 6 x 7 l 1 10 34 23 45 60 57 50 l3 19 29 16 38 53 50 43 l 4 20 30 9 31 46 43 35 l 7 32 42 17 25 34 31 24 l 8 43 53 28 36 37 34 27 l 9 44 54 29 37 38 27 20 l 10 48 58 33 41 42 25 16 l 11 52 62 37 45 46 29 12 l 12 59 69 44 52 53 36 15 l 13 54 64 39 47 48 31 10 (i, i) (i, i + 1) 90 -
"Reduce" step と を比較する。要らなくなった列は捨てる。
x 1 x 2 x 3 x 4 x 5 x 6 x 7 l 1 10 34 23 45 60 57 50 l3 19 29 16 38 53 50 43 l 4 20 30 9 31 46 43 35 l 7 32 42 17 25 34 31 24 l 8 43 53 28 36 37 34 27 l 9 44 54 29 37 38 27 20 l 10 48 58 33 41 42 25 16 l 11 52 62 37 45 46 29 12 l 12 59 69 44 52 53 36 15 l 13 54 64 39 47 48 31 10 (i, i) (i, i + 1) 91 -
"Reduce" step と を比較する。要らなくなった列は捨てる。
x 1 x 2 x 3 x 4 x 5 x 6 x 7 l 1 10 34 23 45 60 57 50 l 3 19 29 16 38 53 50 43 l 4 20 30 9 31 46 43 35 l 7 32 42 17 25 34 31 24 l 8 43 53 28 36 37 34 27 l 10 48 58 33 41 42 25 16 l 11 52 62 37 45 46 29 12 l 12 59 69 44 52 53 36 15 l 13 54 64 39 47 48 31 10 (i, i) (i, i + 1) 92 -
"Reduce" step と を比較する。要らなくなった列は捨てる。
x 1 x 2 x 3 x 4 x 5 x 6 x 7 l 1 10 34 23 45 60 57 50 l 3 19 29 16 38 53 50 43 l 4 20 30 9 31 46 43 35 l 7 32 42 17 25 34 31 24 l 8 43 53 28 36 37 34 27 l 10 48 58 33 41 42 25 16 l 11 52 62 37 45 46 29 12 l 12 59 69 44 52 53 36 15 l 13 54 64 39 47 48 31 10 (i, i) (i, i + 1) 93 -
"Reduce" step と を比較する。要らなくなった列は捨てる。
x 1 x 2 x 3 x 4 x 5 x 6 x 7 l 1 10 34 23 45 60 57 50 l 3 19 29 16 38 53 50 43 l 4 20 30 9 31 46 43 35 l 7 32 42 17 25 34 31 24 l 8 43 53 28 36 37 34 27 l 10 48 58 33 41 42 25 16 l 11 52 62 37 45 46 29 12 l 12 59 69 44 52 53 36 15 l 13 54 64 39 47 48 31 10 最後の行までやってきました。 が上に伝播すると、なんと の列を捨てることができます。 (i, i) (i, i + 1) < l12 94 -
"Reduce" step と を比較する。要らなくなった列は捨てる。
x 1 x 2 x 3 x 4 x 5 x 6 x 7 l 1 10 34 23 45 60 57 50 l 3 19 29 16 38 53 50 43 l 4 20 30 9 31 46 43 35 l 7 32 42 17 25 34 31 24 l 8 43 53 28 36 37 34 27 l 10 48 58 33 41 42 25 16 l11 52 62 37 45 46 29 12 l 13 54 64 39 47 48 31 10 (i, i) (i, i + 1) 95 -
"Reduce" step と を比較する。要らなくなった列は捨てる。
x 1 x 2 x 3 x 4 x 5 x 6 x 7 l 1 10 34 23 45 60 57 50 l 3 19 29 16 38 53 50 43 l 4 20 30 9 31 46 43 35 l 7 32 42 17 25 34 31 24 l 8 43 53 28 36 37 34 27 l 10 48 58 33 41 42 25 16 l 13 54 64 39 47 48 31 10 (i, i) (i, i + 1) 96 -
"Reduce" step と を比較する。要らなくなった列は捨てる。
x 1 x 2 x 3 x 4 x 5 x 6 x 7 l 1 10 34 23 45 60 57 50 l 3 19 29 16 38 53 50 43 l 4 20 30 9 31 46 43 35 l 7 32 42 17 25 34 31 24 l 8 43 53 28 36 37 34 27 l 10 48 58 33 41 42 25 16 l 13 54 64 39 47 48 31 10 列の数が行の数まで減った! (i, i) (i, i + 1) 97 -
まとめ SMAWK algorithm totally monotone 行列の各行の最小値を求める。 1. "Reduce" step :
最小値にならない列を捨てる 2. "Recurse" step : 偶数行のみを取り出して再帰的に解く 3. 最小値にならない部分を捨てる 4. "Interpolate" step : 残りの部分の最小値を求める 行も列も再帰のたびに半分になっていくから、全体で 時間 Θ(N + M) 98 -
そろそろ Monge のおはなしをしよう Monge 行列とは? Gaspard Monge さんが発見した良い性質 Monge totally
monotone monotone 競プロの問題だと、TM だけど Monge でないことはあまりない 競プロの問題だと、monotone だけど TM でないことはあまりない つまり、Monge totally monotone monotone (???) ⟹ ⟹ ⟺ ⟺ 99 -
Monge 行列 (定義) 実数からなる 行列 であって、以下の条件を満たすもの および を満たすすべての整数の組 について、 が成り立つ。
ABC224 B - Mongeness N × M A 1 ≤ i < 1 i ≤ 2 N 1 ≤ j < 1 j ≤ 2 M (i , i , j , j ) 1 2 1 2 A + i ,j 1 1 A ≤ i ,j 2 2 A + i ,j 2 1 A i ,j 1 2 100 -
Monge 行列 (例) A = [ 5 3
8 5 ] なので A + 1,1 A ≤ 2,2 A + 1,2 A 2,1 101 -
Monge は最短路問題で捉えると分かりやすい Monge 単一始点最短路問題 頂点の重み付き有向 DAG があります。頂点 から頂点 へ (
) 移動する コストは で、 は Monge です。 頂点 から頂点 へ移動する最小コストをそれぞれ求めてください。 → 時間のアルゴリズムが存在する N + 1 i j i < j A i,j A 0 1, 2, … , N Θ(N) 102 -
Monge のおきもち A + i ,j 1
1 A ≤ i ,j 2 2 A + i ,j 2 1 A i ,j 1 2 これなに? 103 -
さっきの曲線群で捉えた場合は… Monge のおきもち (1) A + i ,j
1 1 A ≤ i ,j 2 2 A + i ,j 2 1 A i ,j 1 2 A − i ,j 1 1 A ≤ i ,j 1 2 A − i ,j 2 1 A i ,j 2 2 曲線 から曲線 を引いた 差分が単調増加 l j 1 l j 2 104 -
Monge のおきもち (2) A − i ,j
1 2 A ≥ i ,j 1 1 A − i ,j 2 2 A i ,j 2 1 は任意だから、 A − 1,j 2 A ≥ 1,j 1 A − 2,j 2 A ≥ 2,j 1 A − 3,j 2 A ≥ 3,j 1 ⋯ ≥ A − N,j 2 A N,j 1 と同値 i , i 1 2 105 -
Monge のおきもち (2) A − 1,j 2 A
≥ 1,j 1 A − 2,j 2 A ≥ 2,j 1 A − 3,j 2 A ≥ 3,j 1 ⋯ ≥ A − N,j 2 A N,j 1 Monge 最短路問題の気持ちになりましょう。 「頂点 から頂点 へ ( ) 移動するコストが 」とすると、 「区間の左端 を固定して、区間の右端を と動かしたときのコストの増分 は、 が小さいほど (元々の区間の長さ が長いほど) 大きい」 と解釈できる。 i j i < j A i,j i j → 1 j 2 A − i,j 2 A i,j 1 i j − 1 i 106 -
Monge 行列の例 (1) 区間の長さの 乗 2 A = i,j
(j − i)2 A = 0 1 4 9 1 0 1 4 4 1 0 1 9 4 1 0 107 -
Monge 行列の例 (1) 区間の長さの 乗 区間の右端を と動かすときのコス トの増分 : (j
+ 1 − i) − 2 (j − i) = 2 2(j − i) + 1 が小さくなるほど (元々の区間の長さ が長いほど) 大きいので、Monge である。 2 A = i,j (j − i)2 A = 0 1 4 9 1 0 1 4 4 1 0 1 9 4 1 0 j → j + 1 i j − i 108 -
Monge 行列の例 (2) 区間和 例 : A = i,j
X ∑ i≤k<j k X = (4, 1, 3) A = 0 4 0 5 1 0 8 4 3 0 109 -
Monge 行列の例 (2) 区間和 例 : 区間の右端を と動かすときのコス トの増分 :
X − i≤k<j+1 ∑ k X = i≤k<j ∑ k X j が小さくなっても変化しないので、Monge で ある。 A = i,j X ∑ i≤k<j k X = (4, 1, 3) A = 0 4 0 5 1 0 8 4 3 0 j → j + 1 i 110 -
上三角行列になっていますが…? A = 0 4
0 5 1 0 8 4 3 0 のように、左下の一部分が無効値であったとしても Monge 性には問題ないことが 示せる。 111 -
上三角行列になっていますが…? 左下の一部分が無効値であったとしても Monge 性には問題ないことが示せ る。 また、 A =
0 4 5 8 0 1 4 −1 0 3 0 のように、右上の一部分が無効値であったとしても Monge 性には問題ないことが 示せる。 112 -
左下の一部分が無効値であったとしても Monge 性には問題ないことが示せ る。 右上の一部分が無効値であったとしても Monge 性には問題ないことが示せ る。 左上 /
右下 の一部分が無効値の場合は問題があるので注意 113 -
Monge 行列の例 (3) A = i,j −ij A =
−1 −2 −3 −4 −2 −4 −6 −8 −3 −6 −9 −12 −4 −8 −12 −16 114 -
Monge 行列の例 (3) 区間の右端を と動かすとき のコストの増分: −i(j + 1) +
ij = −i が小さくなるほど (元々の区間の長さ が長いほど) 大きいので、Monge である。 A = i,j −ij A = −1 −2 −3 −4 −2 −4 −6 −8 −3 −6 −9 −12 −4 −8 −12 −16 j → j + 1 i j − i 115 -
Monge 行列の例 (4) 区間 例 : min A =
i,j min X i≤k≤j k X = (4, 2, 3, 1) A = 4 2 2 2 2 3 1 1 1 1 116 -
Monge 行列の例 (4) 区間 例 : 区間の右端を と動かすときのコス トの増分 :
X − ( i≤k≤j+1 min k ) X ( i≤k≤j min k ) により最小値が更新される場合のみ考え れば良い。 X − j+1 X ( i≤k≤j min k ) が小さくなるほど (元々の区間の長さ が 長いほど) 大きいので、Monge である。 min A = i,j min X i≤k≤j k X = (4, 2, 3, 1) A = 4 2 2 2 2 3 1 1 1 1 j → j + 1 X j+1 i j − i 117 -
Monge 行列の作り方 (1) 下に凸な関数 に対して、 で定義される行列 下に凸とは から任意に 点取って間を線分で結ぶ と、
は線分より下に来る f(x) A = i,j f(j − i) A f(x) 2 f(x) ⟺ f (x) ≥ ′′ 0 118 -
Monge 行列の作り方 (1) 下に凸な関数 に対して、 で定義される行列 は Monge 例 f(x)
A = i,j f(j − i) A A = i,j 42 A = i,j j − i A = i,j (j − i) − 2 1 A = i,j ∣j − i∣ − 3 ∣j − i∣ 119 -
Monge 行列の作り方 (2) Monge 行列 に対して、 で定義される行列 は Monge Monge
行列 と実数 に対して、 で定義される行列 は Monge 線型結合について閉じている (負数倍は不等号が逆向きになるので、できない) B, C A = B + C A B k ≥ 0 A = k × B A 120 -
Monge 行列の作り方 (3) で定義される行列 は Monge で定義される行列 は Monge 例
: 行全体に何かを足す / 列全体に何かを足す をしても Monge 性には影響ない A = i,j X i A A = i,j X j A A = 4 4 4 4 0 0 0 0 7 7 7 7 3 3 3 3 121 -
Monge 行列の作り方 (4) 単調増加な数列 と単調減少な数列 に対して、 で定 義される行列 例 X
Y A = i,j X × i Y j A A = i,j i × (−j) A = i,j (j − i) = 2 j + 2 i + 2 2 × i × (−j) 122 -
Monge 行列の例 (2) 再び 区間和 例 : 累積和をすると 行全体に何かを足す /
列全体に何かを足す を しても Monge 性には影響ないので、これは Monge A = i,j X ∑ i≤k<j k X = (4, 1, 3) A = 0 4 0 5 1 0 8 4 3 0 A = i,j S − j S i 123 -
Monge 行列の例 (5) 区間和の 乗 正整数列 に対して 例 : 2
X A = i,j X (∑ i≤k<j k ) 2 X = (4, 1, 3) A = 0 16 0 25 1 0 49 16 9 0 124 -
Monge 行列の例 (5) 区間和の 乗 正整数列 に対して 例 : 累積和をすると、
A = i,j (S − j S ) = i 2 S + i 2 S − j 2 2S S i j が Monge かを見れば良くて、 は単調増加なので良い。 2 X A = i,j X (∑ i≤k<j k ) 2 X = (4, 1, 3) A = 0 16 0 25 1 0 49 16 9 0 −S S i j S 125 -
Monge 行列の例 (6) ( 〜 行目の 〜 列目に含 まれる丸の個数) A
= i,j i j i j A = 1 1 0 7 2 1 14 9 3 0 126 -
Monge 行列の例 (6) ( 〜 行目の 〜 列目に含 まれる丸の個数) を増やした時に増える領域を考える
と、 が小さいほど (元々の区間の長さ が長いほど) 大きいので、Monge である。 A = i,j i j i j j i j − i 127 -
Monge が分かってきたところで、問題を解いていこう。 スペースエクスプローラー高橋君 数列 に対して、 行列 を と定義する。 の各行の最小値を求めよ。 a
N × N A A = i,j a + j (i − j)2 A N ≤ 2 × 105 128 -
スペースエクスプローラー高橋君 数列 に対して、 行列 を と定義する。 の各行の最小値を求めよ。 解答 は列に足しているだけなので無視して良い は
の凸関数なので Monge monotone minima で 時間 SMAWK algorithm で 時間 a N × N A A = i,j a + j (i − j)2 A N ≤ 2 × 105 +a j (i − j)2 j − i Θ(N log N) Θ(N) 129 -
今度はこの問題について深掘りしてみましょう… Monge 単一始点最短路問題 頂点の重み付き有向 DAG があります。 頂点 から頂点 へ (
) 移動するコストは で、 は Monge です。 頂点 から頂点 へ移動する最小コストをそれぞれ求めてくださ い。 N + 1 i j i < j A i,j A 0 1, 2, … , N 131 -
Monge の制約がない場合は、DP で解きますね Monge 単一始点最短路問題 普通に集める DP をする dp[0] =
0 dp[i] = dp[j] + A 0≤j<i min { j,i } 132 -
Monge 単一始点最短路問題 普通に集める DP をする このままだと列最小値問題になってしまうので、転置します。 頂点 から頂点 へ (
) 移動するコストは 計算量は dp[0] = 0 dp[i] = dp[j] + A 0≤j<i min { i,j } j i j < i A i,j Θ(N ) 2 133 -
普通に集める DP をする A =
6 9 13 17 3 7 11 3 7 3 134 -
普通に集める DP をする A =
6 9 13 17 3 7 11 3 7 3 135 -
普通に集める DP をする A =
6 9 13 17 3 7 11 3 7 3 136 -
普通に集める DP をする A =
6 9 13 17 3 7 11 3 7 3 137 -
普通に集める DP をする A =
6 9 13 17 3 7 11 3 7 3 138 -
Monge 単一始点最短路問題 とは、辺のコストが のように Monge 行列で与えられたとき、右 のような DP をする問題である。 集める
DP で A = 6 9 13 17 3 7 11 3 7 3 Θ(N ) 2 139 -
さて、遷移行列は Monge なのでした 行最小値問題に変換する 遷移行列 A =
6 9 13 17 3 7 11 3 7 3 は Monge 140 -
行最小値問題に変換する 遷移行列 は Monge つの列に何かを足しても Monge 性に は影響がないから、 列目に を足し
てみよう A 1 i dp[i] A = dp[0] + 6 dp[0] + 9 dp[0] + 13 dp[0] + 17 dp[1] + 3 dp[1] + 7 dp[1] + 11 dp[2] + 3 dp[2] + 7 dp[3] + 3 141 -
行最小値問題に変換する A = 6
9 13 17 9 12 17 12 16 15 Monge 行最小値問題になったので、 SMAWK algorithm で で解ける! Θ(N) 142 -
行最小値問題に変換する A = 6
9 13 17 9 12 17 12 16 15 Monge 行最小値問題になったので、SMAWK algorithm で で解ける! を求めるまで 列目の値は分からない Θ(N) dp[i] i 143 -
を求めるまで 列目の値は分からない A = 6
9 13 17 3 + dp[1] 7 + dp[1] 11 + dp[1] 3 + dp[2] 7 + dp[2] 3 + dp[3] dp[i] i 144 -
を求めるまで 列目の値は分からない A = 6
9 13 17 9 13 17 3 + dp[2] 7 + dp[2] 3 + dp[3] dp[i] i 145 -
を求めるまで 列目の値は分か らない A =
6 9 13 17 9 13 17 12 16 3 + dp[3] dp[i] i 146 -
を求めるまで 列目の値は 分からない A =
6 9 13 17 9 13 17 12 16 15 dp[i] i 147 -
を求めるまで 列目の値は 分からない A =
6 9 13 17 9 13 17 12 16 15 dp[i] i 148 -
これを一般化すると… オンライン Monge 行最小値問題 の Monge 下三角行列 が段階的に与えられる。 行目の最小値を求めると、 列目が与えられる。
(オンライン) それぞれの行の最小値 (がどこにあるか) を求めよ。 N × N A i i 149 -
オンライン・オフライン変換 1. 上半分を再帰的に解く 2. 左半分が使えるようになった 3. 利用可能な正方形領域に対して SMAWK algorithm を適用
左半分での最小値は分かっているので、右半 分の最小値を求めればすぐに行全体の最小値 がわかる! 155 -
オンライン・オフライン変換 1. 上半分を再帰的に解く 2. 左半分が使えるようになった 3. 利用可能な正方形領域に対して SMAWK algorithm を適用
左半分での最小値は分かっているので、右半分での行最小値を求め ればすぐに行全体の最小値がわかる! 列目のみが使用できる状態 行目の行最小値を求めたい これは、最初の問題と全く同じ 4 5, 6, 7 156 -
オンライン・オフライン変 換 1. 上半分を再帰的に解く 2. 左半分が使えるようになった 3. 利用可能な正方形領域に対して SMAWK algorithm
を適用 4. 右半分を再帰的に解く 半分の大きさを 回解くので、計算 量は 2 Θ(N log N) 157 -
にしかならないと思いきや…? LARSCH algorithm オンライン Monge 行最小値問題は 時間で解ける! On-line dynamic programming
with applications to the prediction of RNA secondary structure. Journal of Algorithms, 12(3), pp. 490-515 (1991) 論文の著者 Lawrence L. Larmore Baruch Schieber (論文の著者は 人いません) Θ(N log N) Θ(N) 6 158 -
LARSCH algorithm アイデア : SMAWK algorithm を並列化し、利用可能なところから順番に処理 していく 一旦オンラインであることを忘れてみよう →
SMAWK algorithm で解ける 159 -
オンラインであることを思い出して みよう! 1. 行目の最小値を求めたい 2. 行目の探索すべき範囲を決めるには、 行目と 行目の最小値が必要 3. 行目の最小値を求めるには、
列目 〜 列目が利用可能でなければならない 4. 列目を利用可能にするには、 行目の最 小値が必要 5 5 4 6 6 0 5 5 5 170 -
これで何がうれしいかと言うと… さっきの並列 SMAWK algorithm では… 1. 行目の最小値を求めたい 2. 行目の探索すべき範囲を決めるには、 行目と
行目の最小値が必要 3. 行目の最小値を求めるには、 列目 〜 列目が利用可能でなければならない 4. 列目を利用可能にするには、 行目の最 小値が必要 5 5 4 6 6 0 5 5 5 177 -
偶数行の右端を削ると…? 1. 行目の最小値を求めたい 2. 行目の探索すべき範囲を決めるには、 行目と 行目の最小値が必要 3. 行目の最小値を求めるには、 列目
〜 列目が利用可能でなければならない → 行目の最小値を先に求められる! 5 5 4 6 6 0 4 6 178 -
SMAWK algorithm 1. "Reduce" step : 最小値にならない列を捨てる 2. "Recurse" step
: 偶数行のみを取り出して再帰的に解く 3. 最小値にならない部分を捨てる 4. "Interpolate" step : 残りの部分の最小値を求める ( 回の比較を行う) M − 1 179 -
LARSCH algorithm 1. "Reduce" step : 最小値にならない列を捨てる 2. 各偶数行の右端を、 つ上の行に合わせるように削る
3. "Recurse" step : 偶数行のみを取り出して再帰的に解く 4. 最小値にならない部分を捨てる 5. "Interpolate" step : 残りの部分の最小値を求める (削った部分についても最小になっていないか確認する) 1 180 -
LARSCH algorithm 1. "Reduce" step : 最小値にならない列を捨てる 2. 各偶数行の右端を、 つ上の行に合わせるように削る
3. "Recurse" step : 偶数行のみを取り出して再帰的に解く 4. 最小値にならない部分を捨てる 5. "Interpolate" step : 残りの部分の最小値を求める (削った部分についても最小になっていないか確認する) これら全てを並列にして、計算できるところから計算すれば完成! (投げやり) 1 181 -
"Reduce" step を並列化するには… 1. 列が送られてくる 2. "Reduce" step を進める 3.
一番上の行にはこれ以上要素が追加されないから、一番上の行についての "Reduce" step の結果が確定する 4. 採用されることが確定した列を送って行最小値を得る 216 -
復習 : LARSCH algorithm 1. "Reduce" step : 最小値にならない列を捨てる 2.
各偶数行の右端を、 つ上の行に合わせるように削る 3. "Recurse" step : 偶数行のみを取り出して再帰的に解く 4. 最小値にならない部分を捨てる 5. "Interpolate" step : 残りの部分の最小値を求める (削った部分についても最小になっていないか確認する) 1 218 -
というわけで、LARSCH algorithm ができた LARSCH algorithm 1. "Reduce" step : 最小値にならない列を捨てる
2. 各偶数行の右端を、 つ上の行に合わせるように削る 3. "Recurse" step : 偶数行のみを取り出して再帰的に解く 4. 最小値にならない部分を捨てる 5. "Interpolate" step : 残りの部分の最小値を求める (削った部分についても最小になっていないか確認する) これら全てを並列にして、計算できるところから計算すると、できる noshi91 先生の実装 1 243 -
Monge 単一始点最短路問題 頂点の重み付き有向 DAG があります。頂点 から頂点 へ ( ) 移動
するコストは で、 は Monge です。 頂点 から頂点 へ移動する最小コストをそれぞれ求めてくださ い。 → LARSCH algorithm で で解ける。 N i j i < j A i,j A 1 2, 3, … , N Θ(N) 244 -
Monge の合成 Monge 行列 に対し、 C i,j
K i,j = A + B k min { i,k k,j} = A + B k arg min { i,k k,j } を計算せよ。 最短路で捉えたときのおきもち : 頂点 から頂点 へ 個の辺を通って移動する。 と移動すると き、 回目の移動のコストが で、 回目の移動のコストが である。 A, B i j 2 i → k → j 1 A i,k 2 B k,j 245 -
Monge の合成 (例) A =
, B = 17 44 61 49 53 49 40 30 19 37 26 62 25 7 19 39 14 14 このとき、 C = , K = (実演) 246 -
Monge の合成 (例) A =
, B = 17 44 61 49 53 49 40 30 19 37 26 62 25 7 19 39 14 14 このとき、 C = , K = 54 79 75 42 49 38 54 44 33 1 2 2 1 3 3 3 3 3 247 -
Monge の合成 を つ選び固定すると… Monge 行列 に対し、 を計算せよ。 → これは
Monge 行最小値問題なので、SMAWK algorithm を 回で 時間 j 1 A, B C = i A + B k min { i,k k } N Θ(N ) 2 248 -
Monge の合成 → これは Monge 行最小値問題なので、SMAWK algorithm を 回で 時間
もっと簡単になるよ! N Θ(N ) 2 249 -
Monge の合成には、こんな良い性質があります Monge の合成 Monge 行列 に対し、 で定義される行列 は Monge
最小値を取る位置を としたとき、 である A, B C = i,j A + B k min { i,k k,j } C K = i,j A + B k arg min { i,k k,j } K ≤ i,j K , K ≤ i,j+1 i,j K i+1,j 250 -
Monge の合成 最小値を取る位置を としたとき、 である どういうこと? K = i,j
A + B k arg min { i,k k,j } K ≤ i,j K , K ≤ i,j+1 i,j K i+1,j 251 -
Monge の合成 区間の右端 or 左端が右にずれる ( の右 or 下に行く) ほど、最小値を取る位
置も右にずれる (値が上昇する) K = 1 2 2 1 3 3 3 3 3 区間をずらすとそれにともなって最小値を取る位置もずれる! K 252 -
Monge の合成 に注目 K =
? ここの最小値を調べる : K ≤ i,j K ≤ i,j+1 K i+1,j+1 Θ(N) 253 -
Monge の合成 に注目 K =
? 2 ? ここの最小値を調べる の範囲しか調べなくて良いので、 K ≤ i,j K ≤ i,j+1 K i+1,j+1 1 ≤ K ≤ 2,1 2 ≤ K ≤ 3,2 3 Θ(N) 254 -
Monge の合成 に注目 K =
? 2 2 ? 3 ? ここの最小値を調べる の範囲しか調べなくて良いので、 K ≤ i,j K ≤ i,j+1 K i+1,j+1 1 ≤ K ≤ 1,1 2 ≤ K ≤ 2,2 3 ≤ K ≤ 3,3 3 Θ(N) 255 -
Monge の合成 に注目 K =
1 2 2 ? 3 3 ? 3 ここの最小値を調べる : の範囲しか調べなくて良いので、 K ≤ i,j K ≤ i,j+1 K i+1,j+1 Θ(N) 1 ≤ K ≤ 1,2 3 ≤ K ≤ 2,2 3 Θ(N) 256 -
Monge の合成 に注目 K =
1 2 2 1 3 3 ? 3 3 ここの最小値を調べる : の範囲しか調べなくて良いので、 K ≤ i,j K ≤ i,j+1 K i+1,j+1 Θ(N) 1 ≤ K ≤ 1,3 3 Θ(N) 257 -
Monge の合成 に注目 K =
1 2 2 1 3 3 3 3 3 斜めに埋めていくと、 を 回やるので K ≤ i,j K ≤ i,j+1 K i+1,j+1 Θ(N) Θ(N) Θ(N ) 2 258 -
noshi 式簡易版 LARSCH algorithm LARSCH algorithm から "Reduce" step を抜いたもの
時間かかるが、定数倍が良く、実装も軽い Θ(N log N) 262 -
monotone minima / noshi 式簡易版 LARSCH algorithm のスラ イドアクセス Mo's
algorithm みたいに区間の端を だけ動かす操作が高速にできる場合 ±1 263 -
Monge 辺最短路問題 (全ての ) 頂点の重み付き有向 DAG があります。頂点 から頂点 へ (
) 移動 するコストは で、 は Monge です。 (頂点 から頂点 へ 個の辺を通って移動するときの最小コス ト) を計算してください。 時間 斜めに埋めるテクが使える k k N i j i < j A i,j A dp[k][i] = 1 i k Θ(N ) 2 264 -
Monge 区間 DP (Knuth-Yao speedup) の形の DP ただし、 は単調 Monge
時間 斜めに埋めるテクが使える dp[i][j] = {dp[i][k] + k min dp[k][j]} + A i,j A Θ(N ) 2 266 -
最適二分探索木 Monge 区間 DP で 時間になる が、さらにすごい考察をすることで meldable-heap を用いて 時間
になる Θ(N ) 2 Θ(N log N) 267 -
Monge 辺 最短路問題 Monge グラフ上の -辺最短路長を計算するアルゴリズム – Kyopro Encyclopedia of
Algorithms Alien DP とか呼ばれているやつ IOI Aliens や JOI 春 2023 Chorus など多数の出題例 (ちょうど 辺使うときの最小コスト) が下に凸なので、ラグランジ ュ緩和ができる ラグランジュ緩和すると Monge 最短路問題なので LARSCH algorithm で 時間 辺の数が 個になるようにラグランジュ緩和の を二分探索 k s − t d f(x) = x Θ(N) k λ 268 -
anti-Monge の場合の単一始点最短路 anti-Monge : Monge の不等号が逆向き 行列を左右反転すれば不等号が Monge の向きになるが、「左上の一部領域が無効 値」は
Monge ではない オンライン・オフライン変換により無効値でない領域を取り出せば Monge → オンライン・オフライン変換 + SMAWK で 実は expected になるらしい Θ(N log N) Θ(N) 270