解説を読んでもよく分からなかった人のための「いもす法」の解説
こんばんみんみん。きりみんちゃんです。
最近いもす法が分かったんだけど、検索して出てくる既存のいもす法の解説を読んでも自分で理解するまでは全然意味を理解出来なかったので、もっと理解しやすいいもす法の解説が書けるのではと思った。
いもす法とは
競プロなどで活用出来るアルゴリズムの一つ。
元ネタはいもすさんという方らしい。解説としてよくこのエントリがリンクされる。
どんな問題が解けるの
最終的な計算を行う前に前処理を行う手法の一つ。
主に配列やグラフなどの一部分に対して同一の変更を複数回行う場合に、変更する範囲の最初と最後にだけ変更内容をメモしておき、最後に最初から順番に合算していくことで、少ない計算量で解くことが出来る。
単純な例
1､2､3～Nまでの番号がついた配列がある。配列の値は始めすべて0である。
範囲を指定する整数a,bのQ個のクエリが与えられ、クエリではNaからNbまでを+1する。
クエリ実行後に配列の値はどう変化するか。
入力例
4 3
1 3
2 4
1 2これはつまりサイズ4の配列があり、配列の一部を+1する3つのクエリが与えられている。
単純に数え上げてみる
これは単純に数え上げることも出来る。
まず最初のクエリは1 3なので、配列の1～3までを+1する。
1 1 1 0次は2 4なので、配列の2～4までを+1する。
1 2 2 1最後は1 2なので、配列の1～2までを+1する。
2 3 2 1なので答えは2 3 2 1である。
これをそのままコードで書くとだいたい以下のような感じになると思う。(擬似コードです)
// Q個のクエリを順番に
for (i = 0; i < Q.size; i++) {
Na, Nb = Q[i]
Na -= 1
Nb -= 1
// a～bの範囲を+1していく。
for (j = Na; j <= Nb; j++) {
array[j] += 1
}
}これはNとQが少なければ問題ないけど、最悪の計算量はO(NQ)になるため、AtCoderの問題でNやQが10^5くらいある一般的な問題では間に合わない可能性が高い。
いもす法を使ってみる
毎回すべて処理していたら間に合わないことが分かったので、いもす法では指定された範囲の最初だけを事前に加算し最後の一つ外側を同じだけ減算し、最後にまとめて答えを計算する。
まず最初のクエリは1 3なので、範囲の始まりである1を+1する。そして同時に範囲の終わりの一つ外側である4を-1する。
1 0 0 -1次は2 4なので、配列の2を+1する。4の一つ外側は5だけど、5は配列の外側なので-1する必要がない。
1 1 0 -1最後は1 2なので、配列の1を+1して、3を-1する。
2 1 -1 -1ここまでが前処理。計算量はO(Q)。
最後に全ての値を順番に数えながら答えの配列を作っていく。
まず配列1の値は2なのでそのまま2を出力する。
2次の値は1なので、2 + 1をして3を出力する。
2 3次は-1なので 3 + (-1)で2を出力する。
2 3 2最後の値は-1なので2 + (-1)で1を出力する。
2 3 2 1これが最終的な回答になる。ちゃんと全部数え上げた場合と同じ答えになった！！！！
最後の計算部分の計算量はO(N)。
そして最終的な計算量はO(Q + N)になった！！！！やったね！！！！
これをコードにするとだいたい以下みたいな感じになる。(疑似コードです)
// Q個のクエリを順番に前処理
for (i = 0; i < Q.size; i++) {
Na, Nb = Q[i]
Na -= 1
Nb -= 1
tmpArray[Na] += 1
if (Nb < N) {
tmpArray[Nb + 1] -= 1
}
}
// 数え上げる
array[0] = tmpArray[0]
for (i = 0; i < N; i++) {
array[i] += array[i - 1] + tmpArray[i]
}いろいろな応用
この考え方を利用すれば多少要件が変わっても活用することが出来る。
たとえば上記の問題が、「整数aのQ個のクエリが与えられ、クエリでは配列のNa以降を+1する。」(つまり範囲の終わりがない)という問題であれば、+1の部分だけをメモすればよく、-1の部分は必要なくなる。加算する値は別に+1じゃなくてもいいし、文字列などでもいい。
これをやるだけの問題に、ABC138-DのKiがある。
この問題では配列ではなく木構造が与えられるためグラフの構築と探索の知識が必要だけど、計算自体は例の問題と同じように「加算する値を一番手前だけメモしておき最後に数え上げる」といういもす法で解くことが出来る。