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

はじめに

• dpについて、体系的にまとめられているという噂を聞いて、アルゴリズム実技検定(上エキ編)を買って、パラパラと眺めていたら、いもす法という言葉が出てきた(p41)。個人の考案者のハンドルネームから、そう呼ばれているとのこと。
• いもすさんのホームページを読ませて貰い、累積和の考えを流用して、計算量を削減する方法だと分かったけど、天才肌の人っぽいからポイントのみ説明されて、余分なことは説明されてないので、自分の備忘のために余分な部分を書き加えながら、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)として、本能の赴くままにコードを書くと、以下の通り

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を使うのは変わらないけど、ループを切り離す工夫として、累積和の考え方を使っている。
• ループの部分のみを抜き出して書くと、具体的には、こんな感じ。

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ループ分離のため、ループ①では増減のみをカウントし、ループ②で累積和もどきを計算している。
  • なぜ、「累積和もどき」と表現したかと言えば、本来の累積和の流儀では、累積和の先頭配列の中身は必ず0となり、サイズは元の配列より1大きくなるため。配列guestの先頭の要素が0でない時点で、標準的な「累積和」の作り方に沿っていない。
• 変更後のコード全体は以下のとおり。といっても、forループ以外の部分に変更は無い。

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)を設定して、本の赴くままにコードを書くと、以下の通り。

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)に削減することが出来る。
• 具体的には､ループを以下の通り分解する。

// 増減のみの記録（本家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の図3、図4、図5、図6、図7を参考にしてね。
• 上記により、計算量はO(N + H･W)となった。
• コード全体は、以下の通り。じつは、こっそりと配列msのサイズを1拡大しているよ。コレをしないと、ループ①で、インデックスが配列の範囲外になってエラーになるよ。

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

さいごに

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