Namaran

Code daily. Without assist.

2026-10-19

budget.c

#include <stdio.h>

struct rec { char kind; size_t len; };

static size_t expand(const struct rec *r, size_t n, size_t limit) {
    size_t total = 0;
    for (size_t i = 0; i < n; i++) {
        if (r[i].kind == 'L') {
            total += r[i].len;  // literal bytes are bounded by the input
        } else if (r[i].len <= limit - total) {
            total += r[i].len;  // a run expands one byte len times
        }
    }
    return total;
}

int main(void) {
    const struct rec r[] = {{'R', 60}, {'L', 50}, {'R', 1000}, {'R', 30}};
    printf("%zu\n", expand(r, 4, 100));
}

これは何を出力するでしょうか?

Answer

1140 の1行です。

expand は記録を先頭から順に見ます。kind が 'L' の記録(リテラル)は長さをそのまま total に足し、'R' の記録(ラン)は r[i].len <= limit - total が成り立つときだけ足します。条件を満たさないランは飛ばされるだけで、ループは止まらずに次の記録へ進みます。

最初のラン60は 60 <= 100 を満たすので、total は60になります。次のリテラル50には検査がなく、total は上限の100を超えて110になります。リテラルの長さが入力の大きさで抑えられるというコメントの判断自体は正しいのですが、上限までの残りは入力の大きさと関係なく減っていきます。

3つ目のランで、limit - total は 100 - 110 を計算します。どちらも符号なし整数型の size_t なので、結果は -10 にならず、SIZE_MAX - 9 という巨大な値に回り込みます。符号なし整数の演算結果は、SIZE_MAX + 1 で割った余りになると規格で決まっているからです。1000 <= SIZE_MAX - 9 は真なので1000が足されて total は1110になり、4つ目の30も同じ理由で足されて1140になります。

引き算が負になってそれ以降のランがすべて弾かれると読めば110、上限を超えるランだけが飛ばされると読めば140になります。どちらの読み方も、limit - total が残りの容量を表すのは total <= limit のあいだだけだという前提を見落としています。一度でも上限を超えると残りの容量は最大値近くの値になり、検査はそれ以降のランをすべて通します。リテラルにも同じ検査をかければ、total が limit を超えることはなくなります1。

  1. 展開量に上限を設けるのは、数KBの圧縮ファイルが展開すると数GBにもなるzip爆弾(zip bomb)への対策です。同じバイトの長い繰り返しはごく小さく圧縮できるので、ランはこうしたファイルの材料になります。