Namaran

Code daily. Without assist.

2026-09-01

doubling.c

#include <stdio.h>

int main(void) {
    enum { N = 13 };
    int dist[N + 1], dq[4 * N] = {[2 * N] = 1}, head = 2 * N, tail = 2 * N + 1;
    for (int v = 0; v <= N; v++) {
        dist[v] = N;
    }
    dist[1] = 0;
    while (head < tail) {
        int v = dq[head++];
        for (int w = 0; w <= 1; w++) {
            int u = w == 0 ? 2 * v : v + 1;
            if (u <= N && dist[v] + w < dist[u]) {
                dist[u] = dist[v] + w;
                dq[w == 0 ? --head : tail++] = u;
            }
        }
    }
    printf("%d\n", dist[N]);
}

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

Answer

2 です。

dist[u] は、1 から u に着くまでの費用の合計の最小値です。v からは 2 * v へ費用0で、v + 1 へ費用1で進めます。配列 dq は両端キュー(deque)として使われていて、費用0の移動で dist が小さくなった数は --head で先頭に、費用1の移動で小さくなった数は tail++ で末尾に入ります。先頭に入るのは取り出したばかりの数と同じ費用の数なので、取り出す数の dist は小さい順に並び、dist[13] は最小の費用になります。

その最小の費用は、数を二進法(binary)で書くと読めます。2倍は二進法の末尾に0を付ける操作なので、1の個数は変わりません。1を足すと1の個数は多くても1つしか増えず、繰り上がりがあればかえって減ります。出発点の1は1の個数が1つ、13 = 11012 は3つなので、1を足す移動は少なくとも2回要ります。1 → 2 → 3 → 6 → 12 → 13 と進めば、1を足すのは 2 → 3 と 12 → 13 の2回で済みます。

移動の回数を数えると、この道では5になります。2倍をできるだけ先に続けて 1 → 2 → 4 → 8 と進み、残りを1ずつ足す道でも、費用は5です。このコードが数えているのは費用1の移動だけで、2倍は何回使っても費用に入りません。費用が0と1の2種類しかない移動で、費用0の行き先をキューの先頭に入れて最小の費用を求める方法は、0-1 BFS と呼ばれます。