いもす法について【競技プログラミング】

# はじめに
- dpについて、体系的にまとめられているという噂を聞いて、[アルゴリズム実技検定(上エキ編)](https://book.mynavi.jp/ec/products/detail/id=135840)を買って、パラパラと眺めていたら、いもす法という言葉が出てきた(p41)。個人の考案者のハンドルネームから、そう呼ばれているとのこと。
- [いもすさんのホームページ](https://imoz.jp/algorithms/imos_method.html)を読ませて貰い、[累積和の考え](https://qiita.com/kei_tnk/items/7620e27c77a2bce21e48)を流用して、計算量を削減する方法だと分かったけど、天才肌の人っぽいからポイントのみ説明されて、余分なことは説明されてないので、自分の備忘のために余分な部分を書き加えながら、swiftで実装してみる。

# いもす法による計算量削減例
- 例題は、以下のような感じ
    - 0〜T時間の間に、お客さんがN人来店し、
    - 各お客さんi(i in 0..<N)の入店時間Siと退店時間Ei時間（0≦Si<Ei≦T）が与えられたとき、
    - そのお店にお客さんが最大何人いたかを答えなさい。
    - ただし、客iは時刻「Si」〜「Ei - 1」の間で1名とカウントされ、「Ei」の時刻ではカウントされない。
- 例えば、入力例を下記のようにしてみる。
```
8 5 // 8時間に5人来店
0 3 // 客① 0時入店、3時退店
2 7
1 5
5 8
4 5
```
- 上記について、時刻ごとの人数を格納する配列guest[i](i in 0...T)として、本能の赴くままにコードを書くと、以下の通り
```swift
let (T,N) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0],$0[1])}[0]
var ses:[(Int,Int)] = []
for _ in 0..<N {
    let (s,e) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0],$0[1])}[0]
    ses.append((s,e))
}

var guests = [Int](repeating:0,count:T+1)
for (s,e) in ses { // -- ①外側のforループ（客毎の入退店時間）
    for t in s..<e { // -- ②内側のforループ（客の滞在時間）
        guests[t] += 1
    }
}

print(guests) // [1, 2, 3, 2, 3, 2, 2, 1, 0]
print(guests.max()!) // 3
```
- 上記のとおり、簡単に実装できたけど、二重ループ①②を使っているから、計算量はO(N･T)だね。
- この計算量を、O(N+T)にするのが、いもす法。具体的には、ループ①とループ②を切り離すこととなる。
- 配列guestを使うのは変わらないけど、ループを切り離す工夫として、累積和の考え方を使っている。
- ループの部分のみを抜き出して書くと、具体的には、こんな感じ。
```swift
for (s,e) in ses { // -- ①旧外側のforループ（客毎の入退店時間）
    guests[s] += 1
    guests[e] -= 1
}

for t in 1...T { // -- ②累積和もどきを作成するforループ(0を飛ばしていることに注意)
    guests[t] += guests[t-1]
}
```
- 上記のとおり、forループを分離したことにより、計算量はO(N+T)となる。
    - forループ分離のため、ループ①では増減のみをカウントし、ループ②で累積和もどきを計算している。
    - なぜ、「累積和もどき」と表現したかと言えば、本来の[累積和](https://qiita.com/kei_tnk/items/7620e27c77a2bce21e48)の流儀では、累積和の先頭配列の中身は必ず0となり、サイズは元の配列より1大きくなるため。配列guestの先頭の要素が0でない時点で、標準的な「累積和」の作り方に沿っていない。
- 変更後のコード全体は以下のとおり。といっても、forループ以外の部分に変更は無い。
```swift
let (T,N) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0],$0[1])}[0]
var ses:[(Int,Int)] = []
for _ in 0..<N {
    let (s,e) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0],$0[1])}[0]
    ses.append((s,e))
}

var guests = [Int](repeating:0,count:T+1)
for (s,e) in ses { // -- ①旧外側のforループ（客毎の入退店時間）
    guests[s] += 1
    guests[e] -= 1
}

print(guests) // [1, 1, 1, -1, 1, -1, 0, -1, -1]

for t in 1...T { // -- 累積和のforループ(0を飛ばしていることに注意)
    guests[t] += guests[t-1]
}

print(guests) // [1, 2, 3, 2, 3, 2, 2, 1, 0]
print(guests.max()!) // 3
```

# お次は二次元配列
- いもす法の便利な点は、二次元配列、三次元配列でも、計算量削減が出来ると言うこと。
- 本家HPでは、二次元配列での削減効果の例として、以下が上げられている。
    - 横W×縦Hのフィールド上に、N種類のモンスターがいて、
    - 各モンスターiの出現可能領域(xi,yi)が、(xi in Ai..<Bi , yi in Ci..<Di)で与えられているとき、
    - フィールド上の地点(x,y)において、最大何種類のモンスターが現れる可能性があるか？ 
- 例えば、入力例を下記のようにしてみる
```
8 5 4 // 横8×縦5のフィールド上に4種類のモンスター
0 8 0 5 // 全域に生息するモンスター
3 6 1 5 // 横:3..<6、縦:1..<5に生息するモンスター
1 4 2 4
2 8 3 4
```
- さて、上記について、フィールド上で最大何種類のモンスターが現れるかを格納する二次元配列ms[j][i](i in 0..<W , j in 0..<H)を設定して、本の赴くままにコードを書くと、以下の通り。
```swift
let (W,H,N) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0],$0[1],$0[2])}[0]
var abcds:[(Int,Int,Int,Int)] = []
for _ in 0..<N {
    let (a,b,c,d) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0],$0[1],$0[2],$0[3])}[0] // 1ずらさない
    abcds.append((a,b,c,d))
}

var ms = [[Int]](repeating:[Int](repeating:0,count:W),count:H)

for (a,b,c,d) in abcds { // -- ①　外側のforループ(モンスター別の生息範囲）
    for j in c..<d { // -- ②-1　内側のy軸forループ
        for i in a..<b { // -- ②-2　内側のx軸forループ
            ms[j][i] += 1
        }
    }
}

for m in ms {
    print(m)
}
print(ms.flatMap{$0}.max()!)

///上記の出力
[1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 2, 2, 2, 1, 1]
[1, 2, 2, 3, 2, 2, 1, 1]
[1, 2, 3, 4, 3, 3, 2, 2]
[1, 1, 1, 2, 2, 2, 1, 1]
4
```
- 上記コードでは、3重ループが形成されているので、計算量はO(N･H･W)となっているが、いもす法を利用することで、計算量O(N + H･W)に削減することが出来る。
- 具体的には､ループを以下の通り分解する。
```swift
// 増減のみの記録（本家HPの図3のイメージ)
for (a,b,c,d) in abcds { // -- ①　旧外側のforループ（モンスター別の生息範囲）
    ms[c][a] += 1
    ms[c][b] -= 1
    ms[d][a] -= 1
    ms[d][b] += 1
}

//x軸に沿った累積和もどき（本家HPの図4,図5のイメージ）
for j in 0..<H { // -- ②-1　旧内側のy軸forループ
    for i in 1..<W { // -- ②-2　旧内側のx軸forループ
        ms[j][i] += ms[j][i-1]
    }
}

//y軸に沿った累積和もどき（本家HPの図6,図7のイメージ）
for j in 1..<H { // -- ②-1　旧内側のy軸forループ
    for i in 0..<W { // -- ②-2　旧内側のx軸forループ
        ms[j][i] += ms[j-1][i]
    }
}
```
- 上記のイメージは、[本家HP](https://imoz.jp/algorithms/imos_method.html)の[図3](https://imoz.jp/data/imos_method/2d_imos1.png)、[図4](https://imoz.jp/data/imos_method/2d_imos2.png)、[図5](https://imoz.jp/data/imos_method/2d_imos3.png)、[図6](https://imoz.jp/data/imos_method/2d_imos4.png)、[図7](https://imoz.jp/data/imos_method/2d_imos0.png)を参考にしてね。
- 上記により、計算量はO(N + H･W)となった。
- コード全体は、以下の通り。じつは、こっそりと配列msのサイズを1拡大しているよ。コレをしないと、ループ①で、インデックスが配列の範囲外になってエラーになるよ。
```swift
let (W,H,N) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0],$0[1],$0[2])}[0]
var abcds:[(Int,Int,Int,Int)] = []
for _ in 0..<N {
    let (a,b,c,d) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0],$0[1],$0[2],$0[3])}[0] // 1ずらさない
    abcds.append((a,b,c,d))
}

var ms = [[Int]](repeating:[Int](repeating:0,count:W+1),count:H+1) // 1ずつ拡張する

for (a,b,c,d) in abcds { // -- ①　旧外側のforループ（モンスター別の生息範囲）
    ms[c][a] += 1
    ms[c][b] -= 1
    ms[d][a] -= 1
    ms[d][b] += 1
}

for m in ms {
    print(m) // 出力①
}

/// 本来的には必要ないけど、msのサイズアップ(+1)を反映した
//x軸に沿った累積和もどき
for j in 0..<(H+1) { // -- ②-1　内側のy軸forループ
    for i in 1..<(W+1) { // ②-2　内側のx軸forループ
        ms[j][i] += ms[j][i-1]
    }
}

//y軸に沿った累積和もどき
for j in 1..<(H+1) { // -- ②-1　内側のy軸forループ
    for i in 0..<(W+1) { // ②-2　内側のx軸forループ
        ms[j][i] += ms[j-1][i]
    }
}

for m in ms {
    print(m) // 出力②
}
print(ms.flatMap{$0}.max()!) // 出力③

///出力
出力①
[1, 0, 0, 0, 0, 0, 0, 0, -1]
[0, 0, 0, 1, 0, 0, -1, 0, 0]
[0, 1, 0, 0, -1, 0, 0, 0, 0]
[0, 0, 1, 0, 0, 0, 0, 0, -1]
[0, -1, -1, 0, 1, 0, 0, 0, 1]
[-1, 0, 0, -1, 0, 0, 1, 0, 1]

出力②　(配列のサイズアップ部分が0となっている)
[1, 1, 1, 1, 1, 1, 1, 1, 0]
[1, 1, 1, 2, 2, 2, 1, 1, 0]
[1, 2, 2, 3, 2, 2, 1, 1, 0]
[1, 2, 3, 4, 3, 3, 2, 2, 0]
[1, 1, 1, 2, 2, 2, 1, 1, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]

出力③
4
```

# さいごに
- いもす法って、他の人の投稿とかを見ると、難しそうなことを書いてあったけど、上記のような簡単な例であれば、それ程頭を使わずに理解できるね。
- このくらいのアルゴリズムなら、スッキリ理解できて気持ちよいね。