はじめに
- 「教育的dp問題」の最終問題を解こうとしたら、CHT1の知識が必要らしいので、習得することにした。
- 具体例を見ないでこのアルゴリズムを理解するのは困難だと思うけど、一応、軽く触れると、下記問題を高速に説くアルゴリズム。
- 直線群(fi(x)=ax+b) (i in 0..<N)を前提情報として与えられます。
- (最大値問題の場合、)クエリ作業として、有る値(xj)を与えられたときに、全ての直線群にxjを代入し、その中の最大値を求めよ。つまり、max{fi(xj)|i in 0..<N}を求めるという問題。
CHTを使って解く問題例
-
この問題が最も、分かり易いんじゃないかな？
- 商品価値Cを持つ商品に対し、最も売上を高くする価格Pを設定した場合、その商品の売上高はいくらとなるか？
- なお、N人の顧客(i in 0..<N)がおり、各顧客iは購買意欲Biを持ち、
C+Bi >= Pのとき、その商品を1個買う。 - 商品がM個有るので、それぞれの商品ごとに売上高を答えよ。
- 入力例
5 4 // 5名の顧客、4つのクエリ(商品)
100 200 300 400 500 // 5名の購買意欲
120 370 470 80 // 商品1の商品価値120、商品2の商品価値370、･･･
問題例の解き方
- 購買意欲を降順に並べると、B=[500,400,300,200,100]
- 商品価値をxとしたとき、
- P = x+500の時、1名が買うため、売上は x+500
- P = x+400の時、2名が買うため、売上は 2x+800
・・・・・・・ - P = x+100の時、5名が買うため、売上は 5x+500
- よって、商品価値xについて、求める最大売上は、下図の緑太線となる。
- 商品価値0の場合(x=0)でも、買う奴いるのかよ！と思うかもだけど、まあ、コンテスト問題だし目をつぶってよ。
- もし、適当なコードを組んだら、各クエリ毎に、契約者人数分の直線にxを代入してmax値を算出しないといけないから、工夫しない計算量はO(M･N)となるけど、制約は$N,M≦2×10^5$なので、工夫しないとTLEとなってしまう。
工夫の方法(CVTの考え方)
- 上図を見れば分かると思うけど、5本の直線があるけど、ある値、例えば、x=470に対してyを求める直線は1本(y=5x+500)のみ。よって、直線を追加するたびに、xの領域毎に、適用すべき直線を1つに絞るようなアルゴリズムを実現できれば対応可能。
- なお、そのアルゴリズムで残された直線は、最大値を求めるような問題である上図で有れば、下に凸な形となる。同様に、最小値を求める問題であれば、上に凸な形となる事は創造できるよね。
- そして、そのような凸の領域を新たに切り取るような直線が現れるときは、2点(l、r)もしくは1点(l)or(r)で交わることになる。
- もし、xの傾きが小さい順に直線を追加する場合は、1点(l)のみで交わる。
- この「傾きが単調増加(単調減少)になるように追加する」がCVTのキモです。
- 傾き単調増加の場合に直線を追加する場面
- 下図のように、「青」⇒「緑」⇒「赤」の順で直線が追加されてきた中、更に直線①または直線②を追加する場面を考える。
- 直線①を追加する場合は赤い線との交点、直線②を追加する場合は、緑の線との交点が採用されるべきだけど、それをアルゴリズムで実現するにはどうすれば良いか？
- 「①(or②)と赤い直線(last)との交点」と「赤い直線(last)と緑の直線(second_last)の交点」の位置関係(点線矢印)から判断します。
- ①とlastの交点は、lastとsecond_lastの交点より「右」にあるので、①との交点は生かされ、確定します。
- ②とlastの交点は、lastとsecond_lastの交点より「左」にあるので、②とlastの交点は死にます(不採用)。
- その後、赤い直線は線の履歴から抹消されて、緑の直線をlast、青の直線をsecond_lastとして同じ事を繰り返します。
- これが、CVTのキモです。
- 下図のように、「青」⇒「緑」⇒「赤」の順で直線が追加されてきた中、更に直線①または直線②を追加する場面を考える。
- 分かっちゃえば大したことない話でしょ？
- こうして、たとえば、タプル(交点の座標、直線の傾きa、直線の切片b)を配列として格納すれば、その配列は自動的に交点の座標に昇順で格納。
- ちなみに、１本目は交点ないよね。直線毎に記録される交点って、意味としては、その直線が最大値となる左限ってこと。だから、問題例の場合は、1本目の交点(左限)はx=0にしておこう。
- そして、問題例の２本目(y=2x+800)との交点は、x=0より左にあるので、この時点で、1本目(y=x+500)はお払い箱(lines.removeLast())され、２本目がlastの座につく。
- クエリを実行するときは、この配列に対してlower_boundで検索をかけて、得られた傾きaと切片bを使ってy=ax+bを出せば良いね！
- まあ、計算量に余裕があれば、配列に対して、.firstIndex{$0 >= x}で検索かけても良いけどね。
- こうして、たとえば、タプル(交点の座標、直線の傾きa、直線の切片b)を配列として格納すれば、その配列は自動的に交点の座標に昇順で格納。
解答コード
let (_,_) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0],$0[1])}[0]
var B = readLine()!.split(separator:" ").map{Int($0)!}
var C = readLine()!.split(separator:" ").map{Int($0)!}
// 直線群を作成
var lines:[(Int,Int)] = [] // 直線群は傾き単調増加としておく必要あり
B.sort(by: >)
var i = 0
for b in B {
i += 1
let line = (i,b*i) // 傾き単調増加が確約された
lines.append(line)
}
// CHTインスタンス生成
var cht = CHT<Int>(lines)
// 最大値直線を取得し、クエリ解答生成
for c in C {
let (a,b) = cht.getLine(c)
print(a * c + b,terminator:" ")
}
struct CHT<T:Comparable & Numeric> { // とりあえず、max値を求めるCHT(直線群は傾き単調増加としておく)
// Lineを表すタプルを定義
typealias Line = (a: T, b: T) // 直線として、y = ax + b を格納するよ。
typealias Crss = (c: T, l: Line) // lは最大値直線。cは最大値直線の左限(左隣の直線との交点)。
var lim_left:T = 0 //左限の位置
var lines:[Line] // aが昇順の前提で格納
var crss: [Crss] = []
init(_ lines:[Line]) {
self.lines = lines
build()
}
mutating func build() {
for i in 0..<lines.count {
let newl = lines[i]
var x: T = lim_left
while !crss.isEmpty {
// print(crss.count)
let last = crss.removeLast()
x = cross(last.l, newl)! // ２直線が平行の時はとりあえずないものとして処理
if last.c < x { // 交点が右側なら、取りだしたlastを元に戻して終了
crss.append(last)
break
} // 交点が左側なら、次の周回で、更に１つ前の直線をlastとして再チャレンジ
x = max(x,lim_left) // xが左限以下でループが終わることを回避
}
crss.append((x, newl)) // 新しい直線を交点と共に登録
}
}
// 交点を計算する関数
func cross(_ line_1: Line, _ line_2: Line) -> T? {
let (a1, b1) = line_1
let (a2, b2) = line_2
if a1 == a2 { return nil }
var btm = a1 - a2
var top = b2 - b1
// Numericは割り算できないから、ここで分岐
if T.self == Float.self {
return (top as! Float / (btm as! Float)) as? T
} else if T.self == Int.self {
if btm < 0 { btm = 0 - btm; top = 0 - top } // 分母は絶対正数マン
if top > 0 { top += btm - 1 } // (btm - 1)を加算するのが切り上げ調整。
// 負数の商は元々切り上げになるため、調整不要
return (top as! Int / (btm as! Int)) as? T
} else {
return nil // 他の型はサポート外
}
}
// 最大値直線を返す関数
func getLine(_ x:T)->Line {
// let index = crss.firstIndex { $0.c >= x }!
let index = crss.lastIndex { $0.c <= x }!
let line = crss[index].l
return line
}
}
- まぁ、説明不要でしょ。これを提出したら、300ms程度でAC。
- CHTって、名称は小難しいそうな雰囲気だけど、前項「工夫の方法(CVTの考え方)」で書いたネタって、分かり易いカラクリだったしね。
- 説明するとすれば、最大値を返す関数を、サボってO(N)のお気楽な全探査にしちゃったよ。というのも、Tとして、Floatも対応できるようにしたかったからさ。まぁ、小数だってニブタンは出来るけどさ。
- あぁ、あと、最初はFirstIndexで検索しようとしたけど、対象が見つからないエラーに遭遇するから、lastIndexにしたよ。
おわりに
- CHTって、ロジックは簡単だから、すぐに終わるはずだったのに、swiftの文法自体で詰まったわ。
- 具体的には、TがIntの場合と、Floatの時のcrossの場合分け。最終的には、生成ＡＩの出したアイデア、「if T.self == □□□□.self で場合分け」を使ったよ。見苦しいけど、しゃあない。
- まぁ、これで、「教育的dp問題」の最終問題にチャレンジする資格を得たはず！
おまけ知識
- 構造体CHTにぶち込む直線群の傾きを単調減少にすれば、最小直線を求める事が出来るはず。特に何もイジる必要ないと思うよ。
- あと、直線を１本ずつ追加できるように、改造しておこう。と言っても、buildの中身を分離してappendにして、initを少しいじっただけです。ついでに、外から見れないように、一部の関数や変数をprivate化しておこう。
- さいごに重要な大工事だけど、ニブタンに対応しておこう
- ....また、愚痴になっちゃうけど、swiftのタプルって、Comparableじゃないから、ニブタンにぶち込む配列に使えないんだよね。だから、crssをニブタンで使えない。
- 今回は､わざわざComparableなタプルを作るのが面倒だから、ニブタンだけのためにcrss_cを用意したよ。
- また、ニブタンは配列が昇順か降順かで条件式の向きが「>」「<」で異なるから、どちら向きかをニブタン関数uboundに渡すため、incdecフラグを作ったよ。
struct CHT<T:Comparable & Numeric> { // とりあえず、max値を求めるCHT(直線群は傾き単調増加としておく)
// Lineを表すタプルを定義
typealias Line = (a: T, b: T) // 直線として、y = ax + b を格納するよ。
typealias Crss = (c: T, l: Line) // lは最大値直線（または最小値曲線）。cは直線の左限(左隣の直線との交点)。
typealias Crss_c = T // Crssに対してニブタンしたいのに、タプルはComparableじゃないからさぁ...
private var lim_left:T = 0 //左限の位置
private var lines:[Line] // aが昇順(最小値曲線の場合は降順)の前提で格納
private var crss: [Crss] = []
private var crss_c: [Crss_c] = [] //タプルはComparableじゃないからさぁ....
private var incdec : Bool = true // ニブタンuboundに、aが単調増加(true)か単調減少(false)かを伝える。increaseかdecreaseかどうかでincdec。
init(_ lines:[Line] = []) {
self.lines = lines
build()
}
private mutating func build() {
for i in 0..<lines.count {
append(lines[i])
}
}
mutating func append(_ line:Line) {
let newl = line
var x: T = lim_left
while !crss.isEmpty {
let last = crss.removeLast();let last_c = crss_c.removeLast()
x = cross(last.l, newl)! // ２直線が平行の時はとりあえずないものとして処理
if last.c < x { // 交点が右側なら、取りだしたlastを元に戻して終了
crss.append(last);crss_c.append(last_c)
break
} // 交点が左側なら、次の周回で、更に１つ前の直線をlastとして再チャレンジ
x = max(x,lim_left) // xが左限以下でループが終わることを回避
}
crss.append((x, newl));crss_c.append(x) // 新しい直線を交点と共に登録...タプルはComparableじゃないからさぁ....
if lines.count == 2 && lines[0].a > lines[1].a {incdec = false} // aが単調減少であるフラグ(incdec = false)にする
}
// 交点を計算する関数
func cross(_ line_1: Line, _ line_2: Line) -> T? {
let (a1, b1) = line_1
let (a2, b2) = line_2
if a1 == a2 { return nil }
var btm = a1 - a2
var top = b2 - b1
// Numericは割り算できないから、ここで分岐
if T.self == Float.self {
return (top as! Float / (btm as! Float)) as? T
} else if T.self == Int.self {
if btm < 0 { btm = 0 - btm; top = 0 - top } // 分母は絶対正数マン
if top > 0 { top += btm - 1 } // (btm - 1)を加算するのが切り上げ調整。
// 負数の商は元々切り上げになるため、調整不要
return (top as! Int / (btm as! Int)) as? T
} else {
return nil // 他の型はサポート外
}
}
// 最大値直線を返す関数
func getLine(_ x:T)->Line {
let index = ubound_id(crss_c,x) - 1// タプルはComparableじゃないからさぁ....
let line = crss[index].l
return line
}
func ubound_id<T:Comparable>(_ vs:[T],_ num:T)->Int{ //incdecがtrueの時はvsは昇順、falseのときはvsは降順
var ng = -1 // 探索範囲の左端のindex
var ok = vs.count // 探索範囲の右端のindex
while ok - ng > 1 {
let m = (ng + ok) / 2
if (incdec ? vs[m] > num : vs[m] < num) {ok = m} else {ng = m} // 直線群の傾きの動きに連動させる。単調増加(incdec = true),単調減少(incdec = false)
}
return ok
}
}
-
Convex Hull Trick
- "Convex" と "Hull" のそれぞれの日本語の意味は以下の通りです：
- Convex（凸）: 「凸（とつ）」とは、ある図形や集合が、任意の2点を結ぶ線分が常にその内部にある状態を指します。つまり、全ての内部角が180度未満である形を意味します。
- Hull（船体または外殻）: 「Hull（ハル）」とは、元々は船の船体を指しますが、数学や計算機科学の文脈では「外殻」という意味で使用されます。具体的には、ある集合を囲む最小の凸多角形や曲線を指します。
- これらを組み合わせて「Convex Hull（凸包）」と呼び、与えられた点の集合を含む最小の凸多角形を形成するものを意味します。
- なぜ、"trick"なの?
-
trick という単語は、計算機科学やアルゴリズムの文脈でしばしば使われる表現で、「工夫」や「技法」を意味します。特に「Convex Hull Trick」の場合、この名称は特定の問題を効率的に解決するための巧妙な手法や技法を強調しています。
- 巧妙な技法: Convex Hull Trickは、特定の最適化問題を解くための効率的で巧妙な手法を提供します。これは、単純に力任せの計算を行うのではなく、数学的な特性を活用して計算量を削減する工夫を含んでいます。
- 簡潔さ: 「trick」という言葉は、単に技術的な詳細に言及するのではなく、その手法がいかに簡潔でエレガントかを示すためにも使われます。つまり、直感的に理解しやすいが強力な解決法であることを表現しています。
-
trick という単語は、計算機科学やアルゴリズムの文脈でしばしば使われる表現で、「工夫」や「技法」を意味します。特に「Convex Hull Trick」の場合、この名称は特定の問題を効率的に解決するための巧妙な手法や技法を強調しています。
- "Convex" と "Hull" のそれぞれの日本語の意味は以下の通りです：