Namaran

Code daily. Without assist.

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回だけ確かめます。