2026-11-05
grundy.c
int grundy(int n) {
}
1つの山から、1回に1個か3個か4個の石を2人が交互に取り、取れなくなった人が負けになるゲームを考えます。各局面に次の規則で値を付けます。取れる手が無い局面の値は0とし、それ以外の局面の値は、1手で移れる局面の値のどれとも等しくない最小の非負整数とします。石が n 個の局面の値を返す grundy を書いてください。n は0以上100以下です。
入力例 1
grundy(5)
出力例 1
3
入力例 2
grundy(7)
出力例 2
0
入力例 3
grundy(0)
出力例 3
0
Reference
Reference
int grundy(int n) {
static const int moves[] = {1, 3, 4};
int g[101] = {0};
for (int i = 1; i <= n; i++) {
bool seen[4] = {false};
for (int j = 0; j < 3; j++) {
if (moves[j] <= i) {
seen[g[i - moves[j]]] = true;
}
}
while (seen[g[i]]) {
g[i]++;
}
}
return g[n];
}
石が i 個の局面の値は、i より少ない個数の局面の値だけで決まります。そこで配列 g を0個の側から順に埋めます。g[0] は手が無いので、初期化の0のまま使えます。各 i では、取れる個数 moves[j] が i 以下のときだけ、移った先の値 g[i - moves[j]] に seen で印を付けます。そのあと g[i] を0から1ずつ増やし、印の無い最初の値で止めれば、規則どおりの最小の非負整数になります。これは参考実装で、唯一の正解ではありません。再帰とメモ化で書いても同じ値を返します。
seen の大きさは4で足ります。移れる局面は多くても3つなので、印が付く値は3つ以下です。0から3の4つの値がすべて埋まることはなく、while は seen[3] より先を読みません。入力例1を追うと、g[1] から g[5] は 1, 0, 1, 2, 3 になります。g[5] は移り先 g[4] = 2、g[2] = 0、g[1] = 1 を見て、0から2が埋まっているので3です。g[7] は g[6] = 2、g[4] = 2、g[3] = 1 を見て、0が空いているので0になります。値が0の局面では、手番の人はどう取っても負けます。1
- この値はGrundy数(グランディ数、Grundy number)と呼ばれます。このゲームでは値が7個ごとに 0, 1, 0, 1, 2, 3, 2 を繰り返すので、表を作らずに
n % 7で引く書き方もできます。