NimとGrundy数

KotaTakahashi

2022年12月17日 05:30

こんにちは、株式会社Acompanyの高橋昂汰です。

本記事はAcompany Advent Calendar 2022 17日目の記事となります。

皆様は競技プログラミングをやっていますでしょうか?

私は趣味で競技プログラミングをやっていました。
しかし、最近はコンテストの参加もしばらくできていません。

そこで、リハビリも兼ねて、これまで私があまり解いていなかった問題について学んだことを書こうと思います。

Nimとは

n個のコインの山があり、各山にはコインが$${m_i}$$枚ある。プレーヤーは１つの山を選んで、その山から1枚以上のコインを取り除く。これを2人で交互に行い、コインを取り除けなくなったプレイーヤーが負けになる。

というゲームです。

実はこのゲーム、両者が最善をつくすと仮定した時、ゲームを始める前に初期盤面のみで先手後手のどちらかが勝つかがわかります。
これは、後述するGrundy数で考えると証明することができます。

Grundy数とは

Grundy数とはゲームの盤面を非負整数で表したものになり、各盤面はGrundy数が0ならば負け、0以外であれば勝つ盤面となります。

Grundy数の求め方の説明の前にMex(minimum excluded)を説明します。

Mex(minimum excluded)

Mexとは集合に含まれない最小の非負整数のことです。

$$
mex(\emptyset) = 0
$$

$$
mex(\{1,2\}) = 0
$$

$$
mex(\{0,2,3\})=1 \\
$$

$$
mex(\{0,1,2\})=3
$$

Grundy数の求め方

ある盤面のGrundy数はその盤面から遷移できる盤面のGrundy数の集合のMexになります。

例えば、以下の遷移図があったとすると?に入るGrundy数は遷移先のGrundy数の集合が{1,2,1}であるためMexを求めると0になります。

すなわち、この遷移図となるゲームでは先手は必ず負けてしまうことになります。

Nimの必勝法

実はNimは盤面の各山のコインの枚数のxorがその盤面のGrundy数に対応します。
よって、初期盤面の各山のコインの枚数のxorをとり0であれば後手の勝ち、0以外であれば先手の勝ちになります。

例)初期盤面が以下の状態であった場合、初期盤面のGrundy数はxor(4,3,5) = 10となり、先手必勝になります。

以下、各山のコインの枚数のxorをxorSumとします。

証明

xorSumがGrundy数になることの証明
xorSumの値に注目してみると以下の3つが成り立ちます

xorSumが0の時、1つ以上の石を取り除くとxorSumは0以外の値になる。
xorSumが0以外の時、遷移先のxorSumを0にする石の取り方が存在する。
全ての石がなくなった時、xorSumは0になり負けとなる。

よって、xorSumが0以外の時、遷移先のxorSumが0になる石の取り方が存在することを証明できればxorSumがGrundy数になることを証明できます。

xorSumが0以外の時、遷移先のxorSumが0になる石の取り方が存在することを証明します。

以下の手順で石を取ることでxorを0にすることが可能です。

xorSumの最上位bitが立っている山を一つ選ぶ(xorの性質から必ずそのような山は存在します。)
選んだ山のコインをxorSumの1のbitが立っている桁だけ{0,1}を入れ替えたものにします。

具体例で説明します
各山のコインが(2,4,5)であったとします。
これらを二進数で表現すると2($${10_2}$$),4($${100_2}$$),5($${101_2}$$)
これらのxorを求めると、3となります。
同様に3($${11_2}$$)となります。
手順1として3の最上位bitである2の桁が立っている山を選びます。(コインが2枚ある山を選びます)
手順2としてxorSum($${11_2}$$)の1のbitが立っている桁が反転するようにコインを取ります。
よって操作後のコインは1枚になり、各山のコイン(1,4,5)のxorSumは0になります。

よって、各山のコインの枚数のxorが0以外の時、遷移先のxorが0になる石の取り方が存在するため、xorがGrundy数になることが証明できます。

問題を解いてみる

素因数ゲーム

※問題概要はリンクからご覧ください

解法

この問題は素因数分解を行い、各素因数の指数がNimのコインの枚数と考えることができます。
よって各素因数の指数のxorを取ることでこの問題を解くことができます。

ソースコード
c++

#include <bits/stdc++.h>
using ll = long long;
using namespace std;
vector<pair<ll, ll>> prime_factorize(ll N) {
    vector<pair<ll, ll> > res;
    for (ll a = 2; a * a <= N; ++a) {
        if (N % a != 0) continue;
        ll ex = 0;

        while (N % a == 0) {
            ++ex;
            N /= a;
        }

        res.push_back({a, ex});
    }

    if (N != 1) res.push_back({N, 1});
    return res;
}

int main(){
    ll n;
    cin >> n;
    
    vector<pair<ll, ll> > res = prime_factorize(n);
    
    ll ans = 0;
    for(int i=0;i<res.size();i++){
        ans^=res[i].second;
    }

    cout << (ans==0?"Bob":"Alice")<<endl;
}

対決!!! 飲み比べ

※問題概要はリンクからご覧ください

解法

この問題はNimに取ることができる枚数の制約がついた問題になります。

kを3としたとき、Grundy数は以下のように周期性を持つ。

よって各酒のGrundy数を$${A_i \% (k+1)}$$にすることで、Nimと同じ問題に帰着することができます。

ソースコード
c++

#include <bits/stdc++.h>

int main(){
    int n,k;
    std::cin >> n >> k;
    int ans = 0;
    for(int i=0;i<n;i++){
        int a;
        std::cin >> a;
        ans ^= a%(k+1);
    }
    std::cout << (ans==0?"NO":"YES")<< std::endl;
}

参考

この記事が気に入ったらサポートをしてみませんか？