Misere Nim
(Src/Utility/MisereNim.hpp)

• View this file on GitHub
• Last update: 2025-04-05 14:11:54+09:00
• Include: #include "Src/Utility/MisereNim.hpp"

概要

Misere Nimの勝敗を判定します

Misere Nimとは、「最後の一個をとったら負け」石取りゲームのこと。

$2$ 個以上の石からなる石山が存在すると通常のNimに帰着し、そうでない場合は自明

使い方

enum class GameWinner {
    First,
    Second
}

返り値

template <std::input_iterator It>
GameWinner MisereNim(It first, It last)

標準ライブラリと同じノリでイテレータを入れる

Depends on

• 標準データ型のエイリアス (Src/Template/TypeAlias.hpp)

Verified with

• Test/yukicoder/3090.test.cpp

Code

#pragma once

#include "../Template/TypeAlias.hpp"

#include <concepts>
#include <iterator>

namespace zawa {

enum class GameWinner {
    First,
    Second,
};

template <std::input_iterator It>
GameWinner MisereNim(It first, It last) {
    u64 grundy = 0;
    usize size = 0;
    bool over2 = false;
    for (auto it = first ; it != last ; it++, size++) {
        u64 val = static_cast<u64>(*it);
        over2 |= val >= 2;
        grundy ^= val;
    }
    if (over2) return grundy ? GameWinner::First : GameWinner::Second;
    else return size & 1 ? GameWinner::Second : GameWinner::First;
}

} // namespace zawa

#line 2 "Src/Utility/MisereNim.hpp"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 4 "Src/Utility/MisereNim.hpp"

#include <concepts>
#include <iterator>

namespace zawa {

enum class GameWinner {
    First,
    Second,
};

template <std::input_iterator It>
GameWinner MisereNim(It first, It last) {
    u64 grundy = 0;
    usize size = 0;
    bool over2 = false;
    for (auto it = first ; it != last ; it++, size++) {
        u64 val = static_cast<u64>(*it);
        over2 |= val >= 2;
        grundy ^= val;
    }
    if (over2) return grundy ? GameWinner::First : GameWinner::Second;
    else return size & 1 ? GameWinner::Second : GameWinner::First;
}

} // namespace zawa

Back to top page