2026-10-10
range_shift.c
#include <stdio.h>
struct range { int lo, hi; }; // invariant: lo <= hi
static void set_lo(struct range *r, int lo) {
if (lo <= r->hi) r->lo = lo; // refuse to break the invariant
}
static void set_hi(struct range *r, int hi) {
if (hi >= r->lo) r->hi = hi;
}
int main(void) {
struct range r = {0, 3};
for (int d = 2; d <= 8; d += 3) { // shift right by 2, 5, 8
set_lo(&r, r.lo + d);
set_hi(&r, r.hi + d);
}
printf("%d %d\n", r.lo, r.hi);
}
これは何を出力するでしょうか?
Answer
10 18 です。
set_lo と set_hi は、代入する前に新しい値で lo <= hi が成り立つかを確かめ、成り立たなければ何もせずに戻ります。片方の端を動かすとき、比べる相手はまだ動いていないもう片方の端です。
d = 2 では、set_lo が lo を 2 にしようとし、まだ 3 のままの hi 以下なので通ります。続いて hi が 5 になり、範囲は {2, 5} です。d = 5 では lo を 7 にしようとしますが、hi はまだ 5 なので 7 <= 5 が偽になり、set_lo は代入しません。hi だけが 10 に動いて、範囲は {2, 10} に広がります。d = 8 では lo を 10 にしようとし、10 <= 10 は真なので通ります。hi は 18 になり、10 18 が出力されます。セッターが毎回両端を動かすと考えると、合計 15 ずれて 15 18 になりそうですが、d = 5 の lo が置き去りになった分だけ食い違います。
範囲を右へずらす操作の前と後では、どちらも lo <= hi が成り立ちます。破れるのは lo だけを先に動かした途中の状態で、ずらす量が幅より大きいときに限られます。セッターが呼ばれるたびに不変条件を確かめると、この途中の状態で更新が拒まれ、幅3の範囲が黙って幅8に変わります。不変条件が成り立つべきなのは操作のまとまりの前後なので、右へずらすなら hi を先に動かすか、両端をまとめて設定する関数を用意して、そこで1回だけ確かめます。