尺取り法ってなあに？O(n^2)をO(n)に高速計算する方法！

尺取り法（しゃくとりほう）

ABC353のC問題にて，計算速度を高速化するために用いられており，復習を兼ねてあげています．

尺取り法とは？

部分配列の和や積，部分文字列や連続する要素の組み合わせに関する問題に用いられる．

通常計算をすると二重ループを使うことになり，計算量がO(n^2)となる．

しかし，尺取り法では，2つのポインタを使って，部分配列の範囲を動的に調整するため，一重ループとインナーループを使って効率的に部分配列の計算ができる．その結果，計算量がO(n)となる．

実際のコード

例1）部分配列ABC353-C

問題

尺取り法を使わないコード

#include <iostream>
#include <vector>
using namespace std;

#define rep(i, n) for (int i = 0; i < (n); i++)

int main() {
    // Input
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, n) cin >> a[i];

    long long ans = 0;
    for(int i = 0; i < n; i++) {
        for(int j = i + 1; j < n; j++) {
            ans += (a[i] + a[j]) % 100000000;
        }
    }

    // Output result
    cout << ans << endl;
    return 0;
}

尺取り法を用いたコード

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define rep(i, n) for(int i = 0; i < (n); i++)

int main() {
    //mod
    long long mod = 100000000;

    // Input
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, n) cin >> a[i];

    // Sort
    sort(a.begin(), a.end());

    int r = n;
    long long cnt = 0, ans = 0;
    rep(i, n) {
        r = max(r, i + 1);
        while(r - 1 > i && a[r - 1] + a[i] >= mod) {
            r--;
        }
        cnt += n - r;
    }

    rep(i, n) ans += (long long)(a[i]) * (n - 1);
    ans -= cnt * mod;

    // Output
    cout << ans << endl;
    return 0;
}

2つのポイントで計算が速くなっている．

1. modより大きくなる時をカウントし，後で全ての和からcnt*mod引いている．
2. カウントの仕方が，どの点以上でmodより大きくなるか判断して，その時点でループを抜ける．最大のカウントから，そのポイントまでの距離を引くことで，modより大きくなる数を求めている．

ポインタを求めてそれ以上は計算していないから計算が速い！！