🌟

なぜ累積和では半開区間を使うと良いのか考えてみた

2021/09/27に公開

競技プログラミング

tech

はじめに

競技プログラミングをやっていると、累積和では閉区間ではなく半開区間で実装した方が分かりやすくてミスも少ないって聞きますよね。
自分も半開区間で考えて実装していたりしたのですが、簡単な問題を解いて改めて理解を深めたいと思います。

半開区間・閉区間とは

$5 \leq x < 8$ のように、片方の端の点を含み、もう片方の端の点を含まない区間を半開区間と言います。角括弧と丸括弧を使い、 $[5,8)$ のように表記します。
また、 $5 \leq x \leq 8$ のように、両方の端の点を含む区間を閉区間と言います。こちらは $[5,8]$ のように表記します。

使う問題

累積和を使う簡単な問題です。この問題を半開区間、閉区間それぞれを使って解いてみたいと思います。

解いて比較

半開区間バージョン

#include <bits/stdc++.h>

using namespace std;

int main() {

    int N, K; cin >> N >> K;

    vector<long long> a(N);
    for (int i = 0; i < N; ++i) {
        cin >> a[i];
    }

    // 半開区間で累積和
    vector<long long> s(N+1, 0);
    for (int i = 0; i < N; ++i) {
        s[i+1] = s[i] + a[i];
    }

    long long ans = 0;
    for (int i = 0; i < N-K+1; ++i) {
        ans += s[i+K] - s[i];
    }

    cout << ans << endl;

    return 0;
}

こちらの場合は累積和 $s$ を以下のように扱っています。

$s_0 = 0$
$s_1 = a_0$
$s_2 = a_0 + a_1$
...
$s_N = a_0 + a_1 + a_2 + ... + a_{N-1}$

そして、コード中の以下で部分列の値の合計の総和を求めています。

for (int i = 0; i < N-K+1; ++i) {
    ans += s[i+K] - s[i];
}

これを入力例1にあるように $K=3$ で考えてみると、以下のようになります。

( $i=0$ の時) $s_3 - s_0 = a_0 + a_1 + a_2$ を $ans$ に足す
( $i=1$ の時) $s_4 - s_1 = a_1 + a_2 + a_3$ を $ans$ に足す
( $i=2$ の時) $s_5 - s_2 = a_2 + a_3 + a_4$ を $ans$ に足す

特に場合分けの必要もなく、全てのパターンをfor文の中で取り扱えていることが分かります。

閉区間バージョン

#include <bits/stdc++.h>

using namespace std;

int main() {

    int N, K; cin >> N >> K;

    vector<long long> a(N);
    for (int i = 0; i < N; ++i) {
        cin >> a[i];
    }

    // 閉区間で累積和
    vector<long long> s(N, 0);
    s[0] = a[0];
    for (int i = 0; i < N-1; ++i) {
        s[i+1] = s[i] + a[i+1];
    }

    long long ans = 0;
    ans += s[K-1];
    for (int i = 0; i < N-K; ++i) {
        ans += s[i+K] - s[i];
    }

    cout << ans << endl;

    return 0;
}

こちらの場合は累積和 $s$ を以下のように扱っています。

$s_0 = a_0$
$s_1 = a_0 + a_1$
...
$s_{N-1} = a_0 + a_1 + a_2 + ... + a_{N-1}$

そして、コード中の以下で部分列の値の合計の総和を求めていますが、先ほどと異なっていることが分かります。

ans += s[K-1];
for (int i = 0; i < N-K; ++i) {
    ans += s[i+K] - s[i];
}

先ほどと同じく $K=3$ で考えてみると、以下のようになります。

(for文に入る前) $s_2 = a_0 + a_1 + a_2$ を $ans$ に足す
(for文中で $i=0$ の時) $s_3 - s_0 = a_1 + a_2 + a_3$ を $ans$ に足す
(for文中で $i=1$ の時) $s_4 - s_1 = a_2 + a_3 + a_4$ を $ans$ に足す

半開区間の場合と異なり、最初だけ場合分けをして処理しないといけないことが分かります。
場合分けがあるとそれも含めて考える必要があり、バグを埋め込む可能性が上がりそうです。

まとめ

累積和ではバグを減らすため、半開区間を用いて実装しましょう。
今回は簡単な問題で考えてみましたが、複雑な問題になるほど場合分けを考えずに済むことの恩恵を受けることが多くなると思います。