game/solve_partizan_game.hpp

• View this file on GitHub
• Last update: 2022-09-29 20:20:34+09:00
• Include: #include "game/solve_partizan_game.hpp"

Depends on

• game/dyadic_rational.hpp

Verified with

• test/mytest/partizan.test.cpp
• test_atcoder/abc229h.test.cpp

Code

#include "game/dyadic_rational.hpp"

// 全部 dyadic rational number になるときだけ解ける
// 失敗したときは、empty map が返る
// ・states：興味のある state 全体
// ・get_options：pair<vc<STATE>, vc<STATE>>(STATE), left ops / right ops
template <typename STATE, typename INTEGER, typename F>
unordered_map<STATE, Dyadic_Rational<INTEGER>> solve_partizan_game(
    const vector<STATE>& states, F get_options) {
  using X = Dyadic_Rational<INTEGER>;
  unordered_map<STATE, X> MP;

  bool success = 1;

  auto dfs = [&](auto& dfs, const STATE& s) -> X {
    if (!success) return X();
    if (MP.count(s)) return MP[s];
    vc<X> left, right;
    X xl = -X::infinity(), xr = X::infinity();
    auto [left_ops, right_ops] = get_options(s);
    for (auto&& t: left_ops) chmax(xl, dfs(dfs, t));
    for (auto&& t: right_ops) chmin(xr, dfs(dfs, t));

    if (xl >= xr) {
      // switch
      success = 0;
      MP.clear();
      return X();
    }
    return (MP[s] = X::simplest(xl, xr));
  };

  for (auto&& s: states) dfs(dfs, s);
  return MP;
}

#line 1 "game/dyadic_rational.hpp"
// a+b/2^M の形で持つ
template <typename INTEGER>
struct Dyadic_Rational {
  using X = Dyadic_Rational;
  INTEGER a, b;
  static constexpr int M = std::numeric_limits<INTEGER>::digits - 2;

  Dyadic_Rational(INTEGER a = 0) : a(a), b(0) {}

  // x + y / z
  Dyadic_Rational(INTEGER x, INTEGER y, INTEGER z) : a(x), b(y) {
    auto [q, r] = divmod(b, z);
    a += q;
    b = r;
    b *= (INTEGER(1) << M) / z;
  }

  // x/y
  Dyadic_Rational(INTEGER x, INTEGER y) : Dyadic_Rational(0, x, y) {}

  static X from_ab(INTEGER a, INTEGER b) {
    X x(a);
    x.b = b;
    return x;
  }

  // 比較
  bool operator==(X const& rhs) const { return (a == rhs.a && b == rhs.b); }
  bool operator!=(X const& rhs) const { return !(*this == rhs); }
  bool operator<(X const& rhs) const {
    return (a < rhs.a) || (a == rhs.a && b < rhs.b);
  }
  bool operator<=(X const& rhs) const {
    return (a < rhs.a) || (a == rhs.a && b <= rhs.b);
  }
  bool operator>(X const& rhs) const {
    return (a > rhs.a) || (a == rhs.a && b > rhs.b);
  }
  bool operator>=(X const& rhs) const {
    return (a > rhs.a) || (a == rhs.a && b >= rhs.b);
  }

  // 加法
  friend X operator+(const X& x, const X& y) {
    INTEGER a = x.a + y.a, b = x.b + y.b;
    while (b >= INTEGER(1) << M) {
      ++a;
      b -= INTEGER(1) << M;
    }
    return from_ab(a, b);
  }
  friend X operator-(const X& x, const X& y) {
    INTEGER a = x.a - y.a, b = x.b - y.b;
    while (b < 0) {
      --a;
      b += INTEGER(1) << M;
    }
    return from_ab(a, b);
  }
  friend X operator-(const X& x) {
    INTEGER a = -x.a, b = -x.b;
    while (b < 0) {
      --a;
      b += INTEGER(1) << M;
    }
    return from_ab(a, b);
  }
  X& operator+=(const X& x) { return (*this) = (*this) + x; }
  X& operator-=(const X& x) { return (*this) = (*this) - x; }

  static X simplest(const X& x, const X& y) {
    assert(x < y);
    if (y.a < 0) return -simplest(-y, -x);
    {
      INTEGER l = x.a + 1;
      INTEGER r = (y.b == 0 ? y.a - 1 : y.a);
      if (l <= 0 && 0 <= r) return X(0);
      if (l <= r && 0 <= l) return X(l);
      if (l <= r && r <= 0) return X(r);
    }

    INTEGER l = x.b + 1;
    INTEGER r = (y.b == 0 ? (INTEGER(1) << M) - 1 : y.b - 1);
    if (l == r) return from_ab(x.a, l);
    int k = topbit(l ^ r);
    r &= ~((INTEGER(1) << k) - 1);
    return from_ab(x.a, r);
  }

  static constexpr X infinity() { return from_ab(INTEGER(1) << M, 0); }

  string to_string() {
    ll x = a, y = b, z = INTEGER(1) << M;
    while (y % 2 == 0 && z % 2 == 0) { y /= 2, z /= 2; }
    y += x * z;
    return std::to_string(y) + "/" + std::to_string(z);
  }
};
#line 2 "game/solve_partizan_game.hpp"

// 全部 dyadic rational number になるときだけ解ける
// 失敗したときは、empty map が返る
// ・states：興味のある state 全体
// ・get_options：pair<vc<STATE>, vc<STATE>>(STATE), left ops / right ops
template <typename STATE, typename INTEGER, typename F>
unordered_map<STATE, Dyadic_Rational<INTEGER>> solve_partizan_game(
    const vector<STATE>& states, F get_options) {
  using X = Dyadic_Rational<INTEGER>;
  unordered_map<STATE, X> MP;

  bool success = 1;

  auto dfs = [&](auto& dfs, const STATE& s) -> X {
    if (!success) return X();
    if (MP.count(s)) return MP[s];
    vc<X> left, right;
    X xl = -X::infinity(), xr = X::infinity();
    auto [left_ops, right_ops] = get_options(s);
    for (auto&& t: left_ops) chmax(xl, dfs(dfs, t));
    for (auto&& t: right_ops) chmin(xr, dfs(dfs, t));

    if (xl >= xr) {
      // switch
      success = 0;
      MP.clear();
      return X();
    }
    return (MP[s] = X::simplest(xl, xr));
  };

  for (auto&& s: states) dfs(dfs, s);
  return MP;
}

Back to top page