不偏ゲーム (grundy数) (src/Game/ImpartialGame.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2023-01-21 17:49:49+09:00
• Include: #include "src/Game/ImpartialGame.hpp"

メモ化再帰でgrundy数を計算

Verified with

• test/aoj/0401.test.cpp

Code

#pragma once
#include <map>
#include <algorithm>
#include <vector>
template <typename Game, typename F> struct ImpartialGame {
 std::map<Game, unsigned> mp;
 F f;  // : Game -> std::vector<Game>
 static unsigned mex(std::vector<unsigned> S) {
  std::sort(S.begin(), S.end()), S.erase(std::unique(S.begin(), S.end()), S.end());
  for (unsigned i= 0; i < S.size(); i++)
   if (S[i] != i) return i;
  return S.size();
 }
public:
 ImpartialGame(const F &_f): f(_f) {}
 unsigned eval(Game g) {
  if (mp.count(g)) return mp[g];
  std::vector<unsigned> S;
  for (const auto &_g: f(g)) S.emplace_back(eval(_g));
  return mp[g]= mex(S);
 }
};

#line 2 "src/Game/ImpartialGame.hpp"
#include <map>
#include <algorithm>
#include <vector>
template <typename Game, typename F> struct ImpartialGame {
 std::map<Game, unsigned> mp;
 F f;  // : Game -> std::vector<Game>
 static unsigned mex(std::vector<unsigned> S) {
  std::sort(S.begin(), S.end()), S.erase(std::unique(S.begin(), S.end()), S.end());
  for (unsigned i= 0; i < S.size(); i++)
   if (S[i] != i) return i;
  return S.size();
 }
public:
 ImpartialGame(const F &_f): f(_f) {}
 unsigned eval(Game g) {
  if (mp.count(g)) return mp[g];
  std::vector<unsigned> S;
  for (const auto &_g: f(g)) S.emplace_back(eval(_g));
  return mp[g]= mex(S);
 }
};

Back to top page