LoginSignup
0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@kei_tnk

「教育的dp問題」で最も難しいらしいdpを解く【競技プログラミング】

Posted at

はじめに

  • 2か月前に始めた「教育的dp問題」も終わりに近づいてるけど、最も難しいと噂の問題「Intervals」とご対面しました。
  • 考えてみても分からなかったので、解説に従って解こうと思う。

問題

  • 0と1のみからなる文字数Nの文字列Sを作って、それによる最高得点を求める問題。
  • M個のクエリが与えられ、その内容は以下のとおり。
    • (l r a)の三つの数値が与えられる。Sのl〜r文字目の間に1が含まれれば、点数aが与えられる。
  • 入力例
5 3 // 5文字、3クエリ
1 3 10 // クエリ① 1〜3文字目に1があれば、10点
2 4 -10
3 5 10
  • この場合の解答は20です。
  • 具体的には、S="10001"で、スコアがクエリ①​+クエリ③​=10+10=20 となります。

dpの書き方（解説より）

  • 二次元のdp[i][j]を考えます。dpは最高点を格納します。
    • i：Sのi文字目までが確定した状態。つまり、Sの0..<iの値が決まった状態。
    • j：1がある最後のインデックス。だから、d[4][2]は、S=[1 1 1 0],[1 0 1 0],[0 1 1 0],[0 0 0 1]の組み合わせの中での最高点になるね。当然、j<iだよ。
    • なお、実行済みのクエリは、0-idxに変換後でr<iとなる(l r a)のみとします。つまり、r<iとなるクエリを対象としたとき、dp[i].max()!が正解となるね。当然、最終回答は、dp[N].max()!となる。

コード化する（高速化前）

  • とりあえずは、上記dpを用いて、入力例を解くことだけを目的に自力でコード化する。
extension Array { // 二次元配列の省略記法用
    init(_ cnt: Int, _ v: Element) {
        self = [Element](repeating: v, count: cnt)
    }
    init<T>(_ cnt2:Int, _ cnt1:Int, _ v:T) where Element == [T] {
        self = [[T]](cnt2,[T](cnt1,v))
    }
}

let (N,M) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0],$0[1])}[0]

var A:[(Int,Int,Int)] = []
for _ in 0..<M {
let (a,b,c) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0],$0[1],$0[2])}[0]   
    A.append((a-1,b-1,c)) // 範囲は0-idxに
}

// クエリ配列Aのうち、範囲(l,r)が(l,i-1)となっているものを選び、
// l<=jならばaをスコアに加算し、スコア合計を返す関数
func score(_ i:Int,_ j:Int)->Int{
    var sum = 0
    for (l,r,a) in A {
        if i-1 == r {
            if l <= j { sum += a }
        }
    }
    return sum
}

var dp = [[Int]](N+1,N,0) // 省略記法
// print(0,dp[0]) // 経過確認用print文

for i in 1...N{

    // パターン⓪　作成途中のSの右端が0のとき（dp[i][i-1]以外)
        for j in 0..<(i-1){
            dp[i][j] = dp[i-1][j] + score(i,j)
        }

    // パターン①　作成途中のSの右端が1のとき（dp[i][i-1]のとき）
        var temp = 0
        for j in 0..<(i-1){
            temp = max(temp,dp[i-1][j])
        }
        dp[i][i-1] = temp + score(i,i-1)

    // print(i,dp[i]) // 経過確認用print文
    
}

print(dp[N].max()!)
  • コレで、Nが小さいときは解けます。
  • まぁ、dpの書き方さえヒントを貰えれば、ここまでは書けるよね。
  • でも、計算量を考えると･･･
    • パターン⓪のforループにscore関数が含まれていて、score関数もforループ(計算量O(M))を含むから、結局、$O(N^2･M)$になるね。
    • おや？複数有る解説の一つを見ると、高速化前でO((N+M)･N)になるみたいなことが書いてあったけど...ま、まぁ、気にしない。どうせ、高速化するんだし。

理解のためにdpを見る

  • まず、下記入力を前提とします。
5 3 // 5文字、3クエリ
1 3 10 // クエリ㋐ S[0..<3]に1が有れば、10点
2 4 -10 // クエリ㋑ S[1..<4]に1が有れば、-10点
3 5 10 // クエリ㋒ S[2..<5]に1が有れば、10点
  • 上記入力に対し、i毎のdp[i]は以下のとおり
0 [0, 0, 0, 0, 0]
1 [0, 0, 0, 0, 0]
2 [0, 0, 0, 0, 0]
3 [10, 10, 10, 0, 0]
4 [10, 0, 0, 0, 0]
5 [10, 0, 10, 10, 20]
  • 各iでの動作を考える。
    • i=0 何の操作もないため、初期化のまま全部0。
    • i=1,2 該当クエリが無いので、dp[i]に変化なし
    • i=3 クエリ㋐がヒット（score関数が動作）
      • パターン⓪により、j=0,1で「+10」
      • パターン①により、j=2で、max(0,0)に「+10」
    • i=4 クエリ㋑がヒット
      • パターン⓪により、j=1,2で「-10」
      • パターン①により、j=3で、max(10,10,10)に「-10」
    • i=5 クエリ㋒がヒット
      • パターン⓪により、j=2,3で「+10」
      • パターン①により、j=4で、max(10,0,0,0)に「+10」
  • よし、理解した！

高速化の準備

  • 制約は、$N,M≦10^5$なので、目指すはO(N･logN)かO(N･logM)かO(N･log(N+M))なんだろうな。一番外のforループでNを使うことは確定だから、残りをlogで収めないと駄目。
  • 高速化前のパターン⓪①を見ると、dpは、dp[i][j]とdp[i-1][j]の形しかないね。これはdpのin-place化が使えるパターンだね。
  • じゃあ、検討してみよう。一次元配列dp[j]にin-place化した前提で考えるよ。
    • パターン①のtemp計算は、dp[j]をセグ木に食わせれば、maxクエリでlogNで計算できるね。
    • パターン⓪①のscore関数については、毎回forループを回してO(M)の計算量を使っているけど、大外のfor-iループに連動させて、必要なクエリだけ使えば良いんだから、クエリ全体のforループを回さない形にすれば良いね。
    • 分かったかも！予め、Aの要素(l,r,a)のr順で並べておけば良いのでは？
  • まずは、in-place化（dp[i][j] ⇒　dp[j]）してみます。
    • in-place化によりi-1でのdpを最初に使いたいのは、パターン①の方なので、パターン①の後にパターン⓪を処理する順序にするよ。dp設定より前は変更無いよ。
///前半省略///

var dp = [Int](N,0) // in-place化！
for i in 1...N{

    // パターン①　作成途中のSの右端が1のとき（dp[i-1]のとき）
        var temp = 0
        for j in 0..<(i-1){
            temp = max(temp,dp[j])
        }
        dp[i-1] = temp + score(i,i-1)
        
    // パターン⓪　作成途中のSの右端が0のとき（dp[i-1]以外)
        for j in 0..<(i-1){
            dp[j] = dp[j] + score(i,j)
        }
}
print(dp.max()!)

-　上記のパターン①②を少し書き換えると以下のとおり、スッキリ！
-　スッキリした後の見た目から、遅延セグ木を1つ作れば対処できる方針が思い浮かぶね。

        var temp = 0
        for j in 0..<(i-1){
            temp = max(temp,dp[j]) // セグ木のmaxクエリで対処できる！
        }
        // dp[i-1] = temp + score(i,i-1)
        dp[i-1] = temp

        // for j in 0..<(i-1){
        for j in 0..<i{
            dp[j] = dp[j] + score(i,j) // 遅延セグ木の区間変更クエリ（加算クエリ）で対処できる！
        }

遅延セグ木（区間変更クエリ：加算、区間取得クエリ：最大値）

import Foundation // 遅延セグ木のprtTree等で必要
class LazySegTree {・・・} // 遅延セグ木
extension Array {・・・} // 二次元配列の省略記法用

let (N,M) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0],$0[1])}[0]

var A:[(l:Int,r:Int,a:Int)] = []
for _ in 0..<M {
let (a,b,c) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0],$0[1],$0[2])}[0]   
    A.append((a-1,b-1,c))
}

A.sort{$0.1 > $1.1} // スタック的に、配列のお尻から先に取り出すため、rの降順で並び替えた。0(MlogM)

var dp = LazySegTree(N)

for i in 1...N{

    // 最大値クエリ（区間取得）
    if i > 1 {
        let mx = dp.query(0,i-1)
        dp.update(i-1,mx)
    }

    // 加算クエリ（区間変更）
    while !A.isEmpty && A.last!.r == i-1  {
        let (a,b,x) = A.removeLast()
        dp.add(a,b+1,x)
    }

}

print(max(0 , dp.query(0,N))) // Sの0/1を全て0にすれば負にならないため
                              //「max(0,」で0以上を保証
  • この問題の難しいところは、遅延セグ木を作ることであり、遅延セグ木さえ用意できれば大したことないね。
  • 上記を提出すると、1000ms程度でACだったよ！やった！

おわりに

  • 凄く疲れました。なんだか、とても眠いんだ...
  • 遅延セグ木の一般化のコードがちょっと汚いけど、しばらく放置かな。
  • in-place化は分かってきた気がする。遅延セグ木を使った問題もいくつかやっつけたいね。
  • 「教育的dp問題」も、あと少しだ...気力で頑張る！
0
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?