Top

半開区間 - ぺんぎんノート

半開区間の性質

区間$[l, r)$の範囲の大きさは$r - l$
範囲が$R$の区間は$[i, i + R)$
長さ$N$の配列の区間$[i, i + R)$を参照したいとき、$i \ge 0$かつ$i + R \le N$であれば参照可能
for文の条件式を書くときに半開区間を意識すると、バグが発生しにくい

4. について

たとえば、長さ$N$の数列$a$の要素が$1$であるものの数を数えるとき、次のようなコードを書きます。

int cnt = 0;
for (int i = 0; i < N; i++) if (a[i] == 1) cnt++;

ここで、$1$が連続して$3$つ並ぶものの数を数えたいとします（$(2,1,1,1,1,2)$は$2$個と数えます）。上記のコードをどのように書き換えればいいでしょうか。以下の4パターンが考えられます。

int cnt = 0;
for (int i = 0; i + x < N; i++) {
  if (a[i] == 1 && a[i + 1] == 1 && a[i + 2] == 1) cnt++;
}

int cnt = 0;
for (int i = 0; i < N - x; i++) {
  if (a[i] == 1 && a[i + 1] == 1 && a[i + 2] == 1) cnt++;
}

int cnt = 0;
for (int i = 0; i < N; i++) {
  if (i + x < N && a[i] == 1 && a[i + 1] == 1 && a[i + 2] == 1) cnt++;
}

int cnt = 0;
for (int i = 0; i < N; i++) {
  if (i < N - x && a[i] == 1 && a[i + 1] == 1 && a[i + 2] == 1) cnt++;
}

このとき、xの値はどうすればいいでしょうか。少し考えることで$2$とわかりますが、範囲が$3$にも関わらず$2$を代入しないといけないということで、頭を使う必要が出てきます。これがひとつならいいのですが、他にも考えなければならないことがあると、途端に訳がわからなくなります。そしてバグを埋め込む可能性が高くなります。

ここで、3. の性質を利用することを考えます。「$i + R \le N$が真なら参照可能」の部分です。この性質を利用したコードは以下になります。

int cnt = 0;
for (int i = 0; i + x <= N; i++) {
  if (a[i] == 1 && a[i + 1] == 1 && a[i + 2] == 1) cnt++;
}

for文の条件式にイコールが追加されました。こうしたとき、xに入れる値は「範囲」であるため、何も考えずに$3$にできます。最終的には次のようなコードになります。

int cnt = 0;
for (int i = 0; i + 3 <= N; i++) {
  if (a[i] == 1 && a[i + 1] == 1 && a[i + 2] == 1) cnt++;
}

この書き方の優れているところは、i + 3 <= Nというコードを書いているときに、「右の端点についての条件を書いている」と自覚できることです。それに対し、i < Nという条件が何を表しているのかについて説明するのは意外と大変です。そういった「よくわからないもの」にxが加わるため、余計に訳がわからなくなります。xの部分にてきとーに値を入れて提出し、WAになったことはないでしょうか？

更に優れている点として、逆向きのループにも対応している点があります。もし半開区間で実装しているという自覚がなければ、以下のコードのxに何を入れるかについて少し悩むと思います。

int cnt = 0;
for (int i = x; i >= 0; i--) {
  if (a[i] == 1 && a[i + 1] == 1 && a[i + 2] == 1) cnt++;
}

半開区間を意識した場合

半開区間を意識すると、xには左の端点を入れることがわかります。そして、左の端点の最大値はいくつかを考えたとき、右の端点の最大値が$N$であることを考慮すると、1. や2. の性質から$N - 3$であることがわかります。

int cnt = 0;
for (int i = N - 3; i >= 0; i--) {
  if (a[i] == 1 && a[i + 1] == 1 && a[i + 2] == 1) cnt++;
}

半開区間を意識しない場合

半開区間を意識しない場合、おそらくa[i + 2]の部分からxを求めることを考えます。そして、$i + 2$が$N$未満になるような$i$の最大値はいくつだろうと考え、$i$に$N - 2$や$N - 3$を代入し、$N - 2$は範囲外にアクセスしてしまうということに気が付き、いずれ$N - 3$を初期値にすればいいとわかります。

このように、半開区間を意識しない場合では、行き当たりばったりな実装になってしまうことがよくありますが、半開区間を意識した場合では、順序よく考察し、正しい実装を行えます。

結論

for文の条件式を書くときに半開区間を意識することで、バグが発生しにくくなります。最後に、半開区間を意識した実装と意識していない実装へのリンクを貼っておきます。問題は、AGC034 A - Kenken Raceです。

半開区間を意識した実装：条件式を左の端点に固定しています。とても実装しやすかったです。
半開区間を意識していない実装：コンテスト本番に提出したコード。危なっかしい実装です。