いもす法についてのノート

いもす法

累積和のアルゴリズム。

想定される使用方法としては「任意の配列オブジェクトの幅指定を何度も受け取る」ものに対して用いる。 これで生成されるのは「受け取った際の合計の配列」である。

ここでは１次元０次について解説する。

参考。

imoz.jp

アルゴリズムについて

幅指定の入力において重複が多かったindexの最大値を求める問題を想定する。

幅指定

まず「幅指定で受け取る」というものを説明する。

例として長さ10で幅指定を受け取るとする。

index:

0,1,2,3,4,5,6,7,8,9

value:

0,0,0,1,1,1,1,1,1,0(*)

0,1,1,1,0,0,0,0,0,0

これを幅指定で受け取ると、

１つ目:index(3~8) だから、3,8

２つ目:index(1~3) だから、1,8

となる。

したがって0,9とすれば1で埋められた入力を受け取ることになる。

(*)再度参照

計算

「重複の数」を計算する。

これは単純に各valueの合計を取ればよいだけなので、例の合計は

index:

0,1,2,3,4,5,6,7,8,9

value:

0,1,1,2,1,1,1,1,1,0

したがってindex:3の2が最大値となる。

いもす法の実践

幅指定での計算を累積和的に工夫する。

幅指定に対して「帯」をイメージし、指定indexの終端まで伸びているとする。

ここで、指定indexの終端+1のindexのvalueを-1とする。

この配列を１つ目(3,8)で考えると、

index:

0,1,2,3,4,5,6,7,8, 9

value:

0,0,0,1,0,0,0,0,0,-1

index:3が1でindex:9が-1となっている。

これを累積和で考えると、index:3からindex:8までが1で埋められ、index:9において-1されることによりその地点が0となる。これで整合性がとれることが理解される。

すなわち、一番最初のvalueの例(*)と同じ情報を持っている。

また、１つ目と２つ目の幅指定を受け取った後のいもすのvalueは

0,1,0,1,-1,0,0,0,0,-1

となる。

計算量削減のイメージ

普通、一つ一つ要素を改めなければならないので（（指定回数+1）*配列の長さ）分の計算が必要だが、いもす法だと（指定回数*2+配列の長さ）となる。

配列要素の変更がindex指定の二回分しか行われないので、非常に計算が軽くなる。

感想

天才の発想。一生思いつかんわ…