はじめに
- いつもの出会い系サイトを覗いてみたら、今日はLISちゃんに出会いました。
- LIS(Longest Increase Subsequence)は、LCS(Longest Common Subsequence)のお仲間みたい。
- LCSは2つの文字列(S,T)のそれぞれの文字列の部分文字列のうち、一致する最長文字列の長さを返すアルゴリズム。
- 例えば、S="abcdef"、T="cdabe"であれば、LCSの長さは3となり、LCSは"abe"と"cde"になる。
- LISは整数配列Aの部分配列のうち、単調増加となる最長配列の長さを返すアルゴリズム。
- 例えば、[3 2 5 3 4 9 7 8]であれば、LISの長さは5であり、LISは[2 3 4 7 8]になる。
- LCSは2つの文字列(S,T)のそれぞれの文字列の部分文字列のうち、一致する最長文字列の長さを返すアルゴリズム。
初歩的なLISの解法
- また、生成AIに簡単な例を紹介して貰いました。
- 整数配列をnumsとしたとき、dp[i]はLISの最後の数値をnums[i]とする縛りを追加した場合のLISの長さです。
- nums[0...i]を整数配列としたときのLISの解ではなく、「LISの最後の数値==nums[i]」となるときのLISの長さがdp[i]となるのがポイントです。
func lengthOfLIS(_ nums: [Int]) -> Int {
if nums.isEmpty {
return 0
}
var dp = [Int](repeating: 1, count: nums.count)
for i in 1..<nums.count {
for j in 0..<i {
if nums[i] > nums[j] {
dp[i] = max(dp[i], dp[j] + 1)
}
}
}
return dp.max()!
}
// 使用例
let nums = [10, 9, 2, 5, 3, 7, 101, 18]
print("最長増加部分列の長さは \(lengthOfLIS(nums)) です。")
- dpの遷移の形を見ると、貰うdpですね。
- dpの初期値は、1になっているのもポイントかな。
- 解答がdp[N-1]じゃなく、dp.max()!なのもポイントだね。
- まぁ、上記コードを実行したとき、dp=[1, 1, 1, 2, 2, 3, 4, 4]だからね。
- 例のnumsでのLISの長さは4になるけど、LISを満たす部分配列は[2 5 7 101]とか[2 3 7 18]とか、複数あり得る。もし、最後の要素が18でなく0だったとき、LISはdp[N-1]ではないね。
- 一応書いておくと、numsの最後を0とすると、dp=[1, 1, 1, 2, 2, 3, 4, 1]だよ。
- とりあえず、LISについて理解したよ。ありがとう生成AI!。
教育的なLIS問題
- これです。
- サイズNの配列が2つあります。
- 花の高さを表す配列H
- 花の美しさを表す配列A
- 花の高さが単調増加になるように何本かの花を抜いて、美しさの合計を最大化しなさい。
- Longestではなくなったけど、考え方はLISを使います。
- これは、自力で解いてみます。
let N = Int(readLine()!)!
let H = readLine()!.split(separator:" ").map{Int($0)!}
let A = readLine()!.split(separator:" ").map{Int($0)!}
var dp = A // 初期値は長さ1の代わりにAとします
for i in 1..<N {
for j in 0..<i {
if H[i] > H[j] {
dp[i] = max(dp[i], dp[j] + A[i]) // 長さ1の代わりにA[i]を加えます
}
}
}
print(dp.max()!)
- 出来た！簡単じゃ〜ん...って思うじゃん？
- 提出したらTLEでした。まぁ、条件を見たら$N≦2×10^5$で、forループで$N^2$の計算量になるから、TLEも当然ね。
- つまり、最初に教えて貰った生成AIの解法が中途半端な計算量無視のものだったと言うこと。
高速なLISの解法
- 生成AIを尋問しました。「LISで計算量を削減するテクニックを教えてください！（度下寝）」
- そしたら、こんなんでました。あ、解説の都合上、使用例のnums配列を少し修正しました。
func lengthOfLIS(_ nums: [Int]) -> Int {
var lis: [Int] = []
for num in nums {
let pos = lis.binarySearch(num)
if pos < lis.count {
lis[pos] = num
} else {
lis.append(num)
}
}
return lis.count
}
extension Array where Element: Comparable {
func binarySearch(_ target: Element) -> Int {
var left = 0
var right = self.count - 1
while left <= right {
let mid = left + (right - left) / 2
if self[mid] == target {
return mid
} else if self[mid] < target {
left = mid + 1
} else {
right = mid - 1
}
}
return left
}
}
// 使用例
//let nums = [10, 9, 2, 5, 3, 7, 101, 18]
let nums = [10, 9, 2, 5, 3, 7, 101, 6] // 最後の18を6に入替
print("最長増加部分列の長さは \(lengthOfLIS(nums)) です。")
- おおっと、ニブタンを使うのね!
- Arrayに追加された関数binarySeach()を見ると、c++のupper_bound関数だね。
- 例えば、A=[10 20 30]のとき、A.binarySeach(x)は、
- xが10以下なら0を返し、
- xが11〜20なら1を返し、
- xが21〜30なら2を返し、
- xが31以上なら、3を返す。
- 例えば、A=[10 20 30]のとき、A.binarySeach(x)は、
- で、肝心のlengthOfLIS関数を見ると...よく分からないので、
for num in numsにprint分を書き加えます。
for num in nums {
let pos = lis.binarySearch(num)
if pos < lis.count {
lis[pos] = num
print(lis) // -- print追加(①要素入れ替え)
} else {
lis.append(num)
print(lis) // -- print追加(②要素追加)
}
}
- これで実行すると、
[10] // ②
[9] // ①
[2] // ①
[2, 5] // ②
[2, 3] // ①
[2, 3, 7] // ②
[2, 3, 7, 101] // ②
[2, 3, 6, 101] // ①
最長増加部分列の長さは 4 です。
- おや？lis配列の中身って...最後に出来た[2 3 6 101]をみると、元の配列のnumsの部分配列になってないね。101より前に6が有るからね。
- さすがにコレは理解不能。蟻本を読んだら同様の解法があるから、これで合ってるっぽいね。
- 上記の計算量はニブタンを使ったお陰でO(N･logN)に改善されているけど、いきなりは理解できないので、中間的にニブタン利用前の$O(N^2)$での解法を理解する。
高速なLIS解法の一歩前（ニブタン形式）
- 前記の解法をニブタン利用前の形で解説する。今回は、生成AIはお休みです。
- 今回もdpを使いますが、最初の考え方とは違います。
- 最初のdp[i]は、「LISの最後の数値をnums[i]にする」という縛りを追加した場合のLISの長さ
- 今回のdp[l]は、LISの長さがl+1となる増加部分列の最終要素の最小値(存在しないときはINF)
- 言い換えると、長さ1のLISを作るときのLISの最終要素の最小値がdp[0]と言うこと。
- え〜、頭がふっと-しちゃうよ〜
- いや、落ち着け。まだ慌てるような時間じゃない。そうだ、俺たちには蟻本がいる。
- で、ちゃんと読むと、dp[l]を作るときは、元のnumsを先頭からから読み込んで作っていくんだね。
- あぁ、なんとなく意味が分かったかも。じゃあ、コードを書いてみよう。
func lengthOfLIS(_ nums: [Int]) -> Int {
let inf = 99
let N = nums.count
var dp = [Int](repeating: inf, count: N)
for num in nums {
for l in 0..<N {
if num <= dp[l] {
dp[l] = num
print(dp) // dpの成長過程を表示
break
}
}
}
return dp.filter{$0 < inf}.count
}
// 使用例
let nums = [10, 9, 2, 5, 3, 7, 11, 6]
print("最長増加部分列の長さは \(lengthOfLIS(nums)) です。")
- 実行すると下記の通りで、前記で作ったlisと同様の成長過程を経ることが分かるね。
[10, 99, 99, 99, 99, 99, 99, 99]
[9, 99, 99, 99, 99, 99, 99, 99]
[2, 99, 99, 99, 99, 99, 99, 99]
[2, 5, 99, 99, 99, 99, 99, 99]
[2, 3, 99, 99, 99, 99, 99, 99]
[2, 3, 7, 99, 99, 99, 99, 99]
[2, 3, 7, 11, 99, 99, 99, 99]
[2, 3, 6, 11, 99, 99, 99, 99]
最長増加部分列の長さは 4 です。
- 今回作ったコードの
for lループは明らかにニブタンで代替できるから、生成AIが作ったコードが正しいことが分かったよ。
もう一つの高速なLIS解法（セグ木形式）
- 今回のそもそものターゲットであるこの問題って、単純なLIS(部分配列の長さを最大化)じゃなくて、いわゆる重みのあるLIS(残す部分配列と紐付いた別の要素[美しさ]を最大化)みたいな感じなので、ニブタン形式だと重みの情報を反映出来なくなっちゃうので駄目でした。
- よって、セグ木形式も身につけます。その前に、そもそもセグ木を知らなかったので、内容に触れてみました。まぁ、フェニック木的な感覚よね。いろいろな処理をO(logN)で出来ちゃうよ！という感じ。
- さて、セグ木導入前に、最初のdpを少し変えます。
- 最初のdp[i]は、「LISの最後の数値をnums[i]にする」という縛りを追加した場合のLISの長さ
- ニブタン用のdp[l]は、LISの長さがl+1となる増加部分列の最終要素の最小値(存在しないときはINF)
- セグ木用のdp[h]は、「LISの最後の数値をhにする」という縛りを追加した場合のLISの長さ
- numsの要素は負にならないという前提で、h in 0...nums.max!とします。
- 前記のニブタンdp[l]を前提としてセグ木用のdp[h]を手作業で推移させると、
for iでnums[i]を読み込む毎にこのような推移となるはずです。
- 上の図を見て、セグ木dpは何故こんな推移になるの？と思った人は、そもそもニブタンdpが理解出てないですので、ニブタンdpの説明に戻ってください。
- さて、dp[h]を使った解法を書いてみようか。どう書けば良いかな？
- 例えば、for文でi=5のときdp[7]=3だけど、これは、dp[7]=dp[0..<7].max()! + 1で求められるよね。
func lengthOfLIS(_ nums: [Int]) -> Int {
let H = nums.max()!
var dp = [Int](repeating: 0, count: H + 1)
for i in 0..<nums.count {
let h = nums[i]
dp[h] = dp[0..<h].max()! + 1
print(dp) // dpの成長過程を表示
}
return dp.max()!
}
// 使用例
let nums = [10, 9, 2, 5, 3, 7, 11, 6]
print("最長増加部分列の長さは \(lengthOfLIS(nums)) です。")
- 実行結果
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0]
[0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0]
[0, 0, 1, 0, 0, 2, 0, 0, 0, 1, 1, 0]
[0, 0, 1, 2, 0, 2, 0, 0, 0, 1, 1, 0]
[0, 0, 1, 2, 0, 2, 0, 3, 0, 1, 1, 0]
[0, 0, 1, 2, 0, 2, 0, 3, 0, 1, 1, 4]
[0, 0, 1, 2, 0, 2, 3, 3, 0, 1, 1, 4]
最長増加部分列の長さは 4 です。
- 手作業で推移させた結果と一致した！終了!...ではないね。もともと、セグ木のための前振りだからね。
- 上記コードだと、forループが1つだけど、max関数の計算量が分からんよね。swiftの仕様次第だけど...O(N)みたいです。max関数の計算量がO(logN)なら、セグ木を使う必要もないんだけどね。
- よって、コレをセグ木で高速化します。使うセグ木は、この投稿のおまけで作ったものです。セグ木の説明は省略します。
class SegTree {・・・} // 最大値クエリ用
func lengthOfLIS(_ nums: [Int]) -> Int {
let H = nums.max()!
// var dp = [Int](repeating: 0, count: H + 1)
var st = SegTree(H+1)
for i in 0..<nums.count {
let h = nums[i]
// dp[h] = dp[0..<h].max()! + 1
let lis = st.query(0,h) + 1
st.update(h,lis) // セグ木をアップデート
// print(dp) // dpの成長過程を表示
st.prtAry() // セグ木配列のクエリ対象部分[n...]を表示
}
// return dp.max()!
return st.top // セグ木の頂点（最大値クエリなので最大値）
}
// 使用例
let nums = [10, 9, 2, 5, 3, 7, 11, 6]
print("最長増加部分列の長さは \(lengthOfLIS(nums)) です。")
- うむ、完成！結果も、セグ木導入前と一致したよ。
教育的なLIS問題（再チャレンジ）
- えーと...どぎゃんしたらよかと？
- 単純なLISは単調増加配列が「長く」なる事を優先してたよね。
- でも、この問題は、花の高さが単調増加を満たしつつ、「花の美しさ合計」を最大化しないと駄目。
- もし、どの花の美しさも「1」なら、単純なLISと同じ結果になるね。
- 計算量無視で解いたときは、下記の通りだったよね。
for i in 1..<N {
for j in 0..<i {
if H[i] > H[j] {
dp[i] = max(dp[i], dp[j] + A[i]) // 長さ1の代わりにA[i]を加えます
}
}
}
print(dp.max()!)
- おや？max関数があるね...分かったかも！セグ木に格納する値を高さでなく美しさの合計値にすれば良い！これだ！
class SegTree {・・・} // 最大値クエリ用
let N = Int(readLine()!)!
let H = readLine()!.split(separator:" ").map{Int($0)!}
let A = readLine()!.split(separator:" ").map{Int($0)!}
let Hmax = H.max()! // 追加
// var dp = A // 初期値は長さ1の代わりにAとします
var st = SegTree(Hmax+1) // dpの代わり
for i in 0..<N {
// for j in 0..<i {
// if H[i] > H[j] {
// dp[i] = max(dp[i], dp[j] + A[i]) // 長さ1の代わりにA[i]を加えます
// }
// }
// dp[i]からdp[h]に変えたことにより、「for j 〜 if H[i]>H[j]」の構造が不要になった
let h = H[i]
// 元々のmax関数部分に相当
let oldv = st.query(h,h+1)
let newv = st.query(0,h) + A[i]
if oldv < newv {
st.update(h, newv)
}
}
print(st.top)
- 提出したら200ms程度でACでした。ありがとうございました。
- 上記は、高速化前のコードをベースにメモ書きしましたが、下記では、通常のLIS用コードをベースにメモ書きしました。
for文のとこだけね。元のnums配列はH、nums.countはN、lisはnewvに名称変更しています。また、print部分も削除しています。
for i in 0..<N {
let h = H[i]
let oldv = st.query(h,h+1) // 追加
// let newv = st.query(0,h) + 1 -- 注目点はLISの長さではなくなった
let newv = st.query(0,h) + A[i] // 追加 -- 注目点は美しさの合計値
if oldv < newv { // 追加 -- 長さと異なり、newvが必ずoldvより高いと限らない
st.update(h,newv)
} // 追加
}
おわりに
- LISをセグ木で高速化するのって定番みたいだけど、分かり易い解説が見つからなかったから、自分でdp[h]をdp[l]と比較する図を書いちゃったよ。
- 自画自賛だけど、現状、教育的DP問題のQ:Flowers」の初心者向け解説としては、ネット上で最も分かり易いものとなったのでは？
- 今回は、満足の出来です。
おまけ
- 高速化したのは良いけど、LISの中身の配列を解答する場合はどうすれば良いか？
- セグ木は、高速化の代わりにインデックス情報が欠落するから、ニブタン方式を使うのが筋だね。
- 繰り返しになるけど、ニブタンで高速化するLISのコードを書きます。生成AIのコードは、若干好みに合わないので、書き換えてます。
- まず、Arrayのextensionを変えます。
extension Array where Element: Comparable {
func ubound(_ x: Element) -> Int { // vsは昇順とする
var ng = -1 // 探索範囲の左端のindex
var ok = self.count // 探索範囲の右端のindex
while ok - ng > 1 {
let m = (ng + ok) / 2
if self[m] > x {ok = m} else {ng = m} //upper_bound
}
return ok
}
init(_ cnt: Int, _ v: Element) {
self = [Element](repeating: v, count: cnt)
}
}
- 関数本体も、Arrayの関数名変更に合わせて、ちょっとだけ修正します。それに、生成AIが選んだ変数lisも中身がLISじゃないのにlisを使うのは気持ち悪いので、今回変えます。ただのメモだから、memで良いよね。
func lengthOfLIS(_ nums: [Int]) -> Int {
var mem: [Int] = []
for num in nums {
let pos = mem.lbound(num)
if pos < mem.count {
mem[pos] = num
} else {
mem.append(num)
}
}
return mem.count
}
- つづいて、LISの中身を復元させる機能を追加したコードはこちら！
- あたらしく、dp[i]を追加しています。d[i]がLISの最後にくるとした場合、その一つ手前のLISの値はなにか？を記録する配列です。最後に、お尻側から復元していきます。
func lengthOfLIS(_ nums: [Int]) -> Int {
var mem: [Int] = []
var dp = [Int](nums.count,-1) // 追加①numをlis[pos]に格納したとき、mem[pos-1]の値を格納する
for (i,num) in nums.enumerated() {
let pos = mem.ubound(num)
if pos < mem.count {
mem[pos] = num
if pos > 0 {dp[i] = mem[pos-1]} // 追加② -- 追加①記載のとおり
} else {
mem.append(num)
if mem.count > 1 {dp[i] = mem[mem.count-2]} // 追加③ -- 追加①記載のとおり
}
}
///追加④作成したdpから中身を復元する。お尻から復元しているため、最後に反転させる。
var LIS_r:[Int] = []
var x = mem.last!
for i in (0..<nums.count).reversed() {
if x == nums[i] {
LIS_r.append(x)
x = dp[i]
}
if x == -1 {break}
}
let LIS = LIS_r.reversed().map{$0} // 反転
print(LIS) // [2, 3, 7, 11] -- LISの中身
/// ここまで追加④
return mem.count
}
let nums = [10, 9, 2, 5, 3, 7, 11, 6]
print("最長増加部分列の長さは \(lengthOfLIS(nums)) です。")