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

# はじめに
- 2か月前に始めた「[教育的dp問題](https://atcoder.jp/contests/dp/tasks)」も終わりに近づいてるけど、最も難しいと噂の問題「[Intervals](https://atcoder.jp/contests/dp/tasks/dp_w)」とご対面しました。
- 考えてみても分からなかったので、解説に従って解こうと思う。

# 問題
- `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の書き方（[解説](https://kyopro-friends.hatenablog.com/entry/2019/01/12/231106)より）
- 二次元の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を用いて、入力例を解くことだけを目的に自力でコード化する。
```swift
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]は以下のとおり
```swift
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化](https://qiita.com/kei_tnk/items/9a06d3e12dd83320fb95)が使えるパターンだね。
- じゃあ、検討してみよう。一次元配列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設定より前は変更無いよ。
```swift
///前半省略///

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()!)
```
-　上記のパターン①②を少し書き換えると以下のとおり、スッキリ！
    -　スッキリした後の見た目から、[遅延セグ木](https://qiita.com/kei_tnk/items/8c8ead5d196649f346cf)を1つ作れば対処できる方針が思い浮かぶね。
```swift
        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) // 遅延セグ木の区間変更クエリ（加算クエリ）で対処できる！
        }
```

# 遅延セグ木（区間変更クエリ：加算、区間取得クエリ：最大値）
- 詳しくは、[遅延セグ木の投稿](https://qiita.com/kei_tnk/items/8c8ead5d196649f346cf#%E3%81%8A%E3%81%BE%E3%81%91%E5%8C%BA%E9%96%93%E5%8A%A0%E7%AE%97%E5%8C%BA%E9%96%93%E6%9C%80%E5%A4%A7%E5%80%A4%E3%81%AE%E5%A0%B4%E5%90%88)を見てね。
- 下記はこの遅延セグ木を利用したコード。
```swift
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だったよ！やった！

# おわりに
- 凄く疲れました。なんだか、とても眠いんだ...
- [遅延セグ木の一般化のコード](https://qiita.com/kei_tnk/items/8c8ead5d196649f346cf#%E9%81%85%E5%BB%B6%E3%82%BB%E3%82%B0%E6%9C%A8%E3%82%92%E4%B8%80%E8%88%AC%E5%8C%96%E3%81%99%E3%82%8B)がちょっと汚いけど、しばらく放置かな。
- in-place化は分かってきた気がする。遅延セグ木を使った問題もいくつかやっつけたいね。
- 「[教育的dp問題](https://atcoder.jp/contests/dp/tasks)」も、あと少しだ...気力で頑張る！