misère Nim
(include/emthrm/game/misere_nim.hpp)

• View this file on GitHub
• Last update: 2023-02-23 21:59:12+09:00
• Include: #include "emthrm/game/misere_nim.hpp"

ニムのルールの内、操作できなくなった方を勝ちとするものである。

時間計算量

$O(N)$

仕様

名前	戻り値
template <typename T> bool misere_nim(const std::vector<T>& a);	盤面が $A$ のときの misère Nim で先手が勝利するか。

参考文献

• http://winjii.hatenablog.com/entry/2016/05/29/143653

Depends on

• ニム (nim) (include/emthrm/game/nim.hpp)

Code

#ifndef EMTHRM_GAME_MISERE_NIM_HPP_
#define EMTHRM_GAME_MISERE_NIM_HPP_

#include <algorithm>
#include <vector>

#include "emthrm/game/nim.hpp"

namespace emthrm {

template <typename T>
bool misere_nim(const std::vector<T>& a) {
  std::vector<T> positive;
  positive.reserve(a.size());
  for (const T e : a) {
    if (e > 0) positive.emplace_back(e);
  }
  if (positive.empty()) [[unlikely]] return true;
  return *std::max_element(positive.begin(), positive.end()) == 1 ?
         positive.size() % 2 == 0 : nim(positive);
}

}  // namespace emthrm

#endif  // EMTHRM_GAME_MISERE_NIM_HPP_

#line 1 "include/emthrm/game/misere_nim.hpp"



#include <algorithm>
#include <vector>

#line 1 "include/emthrm/game/nim.hpp"



#line 5 "include/emthrm/game/nim.hpp"

namespace emthrm {

template <typename T>
bool nim(const std::vector<T>& a) {
  long long x = 0;
  for (const T e : a) x ^= e;
  return x != 0;
}

}  // namespace emthrm


#line 8 "include/emthrm/game/misere_nim.hpp"

namespace emthrm {

template <typename T>
bool misere_nim(const std::vector<T>& a) {
  std::vector<T> positive;
  positive.reserve(a.size());
  for (const T e : a) {
    if (e > 0) positive.emplace_back(e);
  }
  if (positive.empty()) [[unlikely]] return true;
  return *std::max_element(positive.begin(), positive.end()) == 1 ?
         positive.size() % 2 == 0 : nim(positive);
}

}  // namespace emthrm

Back to top page