Namaran

Code daily. Without assist.

2026-11-05

grundy_table.c

#include <stdio.h>

int main(void) {
    int g[10] = {0};
    for (int n = 0; n < 10; n++) {
        int seen[3] = {0};
        for (int m = 2; m <= 3 && m <= n; m++) {
            seen[g[n - m]] = 1;
        }
        while (seen[g[n]]) {
            g[n]++;
        }
        printf("%d", g[n]);
    }
    printf("\n");
}

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

Answer

Output

0011200112

内側の for は、石が n 個の山から2個か3個を取ったあとの局面 n - m を調べ、その値 g[n - m] に印を付けます。続く while は g[n] を0から1ずつ増やし、印の無い最初の値で止まります。g[n] は、1手で移れる局面の値に現れない最小の非負整数です。これは「2個か3個取る」石取りゲームのGrundy数1で、0の局面は手番の人が負けます。

ループの条件 m <= n により、石が2個未満の山では内側のループが一度も回りません。n = 0 だけでなく n = 1 も、印が1つも無いまま g[1] = 0 になります。石が1個残っていても、1個は取れないので打てる手がありません。

あとは順に埋まります。g[2] は g[0] = 0 だけを見て1、g[3] は g[1] と g[0] がどちらも0なので1です。g[4] は g[2] = 1 と g[1] = 0 を見て2、g[5] は g[3] と g[2] がどちらも1なので0、g[6] は2と1を見て0になります。g[5] と g[6] が g[0] と g[1] と同じ0なので、ここから先は5個ごとに 0 0 1 1 2 を繰り返します。

見慣れた「1〜k 個を取れる」ゲームでは値が n % (k + 1) になり、0は k + 1 個ごとに1回しか現れません。その形に引きずられて g[1] = 1 から始めると、g[2] 以降もすべてずれます。1個を取れないこのゲームでは、5個ごとに0が2つ続きます。

  1. Grundy数(グランディ数、Grundy number)は、手が無い局面を0とし、それ以外の局面では1手で移れる局面のGrundy数に現れない最小の非負整数とする値です。0の局面からはどう打っても0でない局面に移り、0でない局面からは0の局面に移る手があるので、0かどうかで手番の人の勝ち負けが決まります。