sataniC++

C++、競プロ、数学などについて色々考えたりします。

Imos法(いもす法)

概要

累積和を用いて複数の要素の重なり・深さなどを計算します。


使える状況

括弧のみの文字列("((()(())))"など)の括弧の深さや、ある場所への人の出入り時刻がわかっているときの最多人数など、複数の要素がどれだけ重なっているかを効率よく調べるときなどに使うことができます。


説明

概要にあるような「複数の要素の重なり」を計算するときは、単純に考えると、

”各要素について範囲内のカウントを1足す”

という方法を考えることが出来ます。このとき、計算量は
O(要素の個数\times範囲の長さ)
となりますが、それよりももっと早い方法があります。それがいもす法と呼ばれるアルゴリズムを使う方法です。


いもす法では、基本となる配列に「+1」や「-1」といった前のデータとの差分を入れておき、その配列の累積和をとることで同様の結果を得ることが出来ます。

このときの計算量は
O(要素の個数+範囲の長さ)
と、先ほどよりも結構小さくなっていることがわかります。


なお、累積和についてはこちらを参照してください。
satanic0258.hatenablog.com

コード(C++)

//要ヘッダ:vector
std::vector<int> getCumSum(std::vector<int> baseImos){
    int baseSize = baseImos.size();
    std::vector<int> cumSum(baseSize, 0);
    
    cumSum[0] = baseImos[0];
    for(int i=1; i<baseSize; ++i){
        cumSum[i] = cumSum[i-1] + baseImos[i];
    }
    return cumSum;
}

コードの説明

このコード自体は累積和を求めるものと変わりありません。


具体例

N個の積み木を積んだとき、各座標で縦にどれくらい重なっているかを調べる。

競プロの問題を少し意識した(ような)問題にしてみました。
(微妙に問題文がわかりにくい)

入力が次のとおりで、
--

N\\
P_1\ \ L_1\\
\vdots\\
P_{N-1}\ \ L_{N-1}\\
--
Nを積み木の個数、i番目の積み木に対してP_iを積み木の左端の座標、L_iを積み木の長さとしたとき、
各座標で縦にどれくらい重なっているかをスペース区切りで出力します。
なお、簡単のために積み木は座標0から9までの範囲に収まるものとしています。

#include <iostream>
#include <vector>

std::vector<int> getCumSum(std::vector<int> baseImos){
    int baseSize = baseImos.size();
    std::vector<int> cumSum(baseSize, 0);
    
    cumSum[0] = baseImos[0];
    for(int i=1; i<baseSize; ++i){
        cumSum[i] = cumSum[i-1] + baseImos[i];
    }
    return cumSum;
}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    
    int w = 10;
    int n, blockPos, len;
    std::cin >> n;
    std::vector<int> base(w+1, 0);
    for(int i=0; i<n; ++i){
        std::cin >> blockPos >> len;
        ++base[blockPos];
        --base[blockPos+len];
    }
    
    std::vector<int> depth(getCumSum(base));
    for(int i=0; i<w; ++i){
        std::cout << depth[i] << " ";
    }
    std::cout << "\n";
    return 0;
}

入力

5
0 2
1 4
2 3
4 4
7 1

出力

1 2 2 2 3 1 1 2 0 0 

入力に従って積み木を配置していくと、次の図のようになることがわかります。
f:id:satanic0258:20160416151520p:plain
よって、縦方向の重なりは確かに出力のようになることがわかりますね。


備考

いもす法は、上記のような場合に加えて多次元の場合についても適応することが出来ます。
詳しくは、こちらのサイトを参照してみてください。
いもす法 - いもす研 (imos laboratory)


あとがき

いもす法は、何かと役に立つ面が多かったりします(たまたまそういう問題ばっかり解いていたのかもしれませんが)。
そんなに複雑なアルゴリズムでもないので、サクッと覚えてしまいましょう。


この記事ですが、新年度であったり、いもす法の具体例があまり思いつかなかったりしてしまい、少しブログの更新に時間が空いてしまいました。
あまり記事のことを考えていて結局他のことに時間を割けなくなってしまっては本末転倒なので、気軽にやっていこうと思います。