🌟

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

2021/09/27に公開約2,800字

はじめに

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

https://qiita.com/drken/items/56a6b68edef8fc605821

半開区間・閉区間とは

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

使う問題

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

https://atcoder.jp/contests/abc037/tasks/abc037_c

解いて比較

半開区間バージョン

#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_2ansに足す
  • (i=1の時) s_4 - s_1 = a_1 + a_2 + a_3ansに足す
  • (i=2の時) s_5 - s_2 = a_2 + a_3 + a_4ansに足す

特に場合分けの必要もなく、全てのパターンを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_2ansに足す
  • (for文中でi=0の時) s_3 - s_0 = a_1 + a_2 + a_3ansに足す
  • (for文中でi=1の時) s_4 - s_1 = a_2 + a_3 + a_4ansに足す

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

まとめ

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




Discussion

ログインするとコメントできます