game/solve_partizan_game.hpp

• View this file on GitHub
• Last update: 2024-11-16 13:34:11+09:00
• Include: #include "game/solve_partizan_game.hpp"
• Link: https://qoj.ac/contest/1828/problem/9567

Depends on

• game/dyadic_rational.hpp
• game/number_and_star.hpp
• other/mex.hpp

Verified with

• test/1_mytest/partizan.test.cpp

Code

#include "game/number_and_star.hpp"

// number, star でいい感じに計算できたときだけ成功
// 失敗したときは、empty map が返る
// ・states：興味のある state 全体
// ・get_options：pair<vc<STATE>, vc<STATE>>(STATE), left ops / right ops
// https://qoj.ac/contest/1828/problem/9567
template <typename STATE, typename F>
map<STATE, Number_And_Star> solve_partizan_game(const vector<STATE>& states, F get_options) {
  using X = Number_And_Star;
  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;
    auto [lop, rop] = get_options(s);
    for (auto&& t: lop) left.eb(dfs(dfs, t));
    for (auto&& t: rop) right.eb(dfs(dfs, t));
    auto [ok, t] = X::from_options(left, right);
    if (!success) return X{};
    if (!ok) {
      // print("FAILED");
      // print(s);
      // print("LEFT");
      // for (auto& t: lop) {
      //   X x = dfs(dfs, t);
      //   print(t, x.to_string());
      // }
      // print("RIGHT");
      // for (auto& t: rop) {
      //   X x = dfs(dfs, t);
      //   print(t, x.to_string());
      // }
      success = 0;
      return X();
    }
    MP[s] = t;
    return MP[s] = t;
  };

  for (auto&& s: states) dfs(dfs, s);
  if (!success) MP.clear();
  return MP;
}

#line 1 "game/solve_partizan_game.hpp"

#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(X x, X y, bool include_x = false, bool include_y = false) {
    if (include_x && x != -infinity()) {
      // eps を引く, あとでもっと小さい eps を使っている !
      x = x - from_ab(0, 2);
    }
    if (include_y && y != infinity()) {
      // eps を足す
      y = y + from_ab(0, 2);
    }
    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 1 "other/mex.hpp"
int mex(const vc<int>& A) {
  int n = len(A);
  vc<bool> aru(n + 1);
  for (auto& x: A)
    if (x < n) aru[x] = 1;
  int mex = 0;
  while (aru[mex]) ++mex;
  return mex;
}
#line 3 "game/number_and_star.hpp"

struct Number_And_Star {
  using A = Dyadic_Rational<ll>;
  // a + *b
  A a;
  int b;
  using T = Number_And_Star;

  Number_And_Star(A a = 0, ll b = 0) : a(a), b(b) {}
  T& operator+=(const T& p) {
    a += p.a, b ^= p.b;
    return *this;
  }
  T& operator-=(const T& p) {
    a -= p.a, b ^= p.b;
    return *this;
  }
  T operator-() const { return T(-a, b); }
  bool operator==(const T& p) const { return (a == p.a && b == p.b); }

  // {計算できたか, 値}
  static pair<bool, T> from_options(vc<T> left_ops, vc<T> right_ops) {
    A xl = -A::infinity(), xr = A::infinity();
    vc<int> Lb, Rb;
    for (auto&& t: left_ops) {
      if (chmax(xl, t.a)) Lb.clear();
      if (xl == t.a) Lb.eb(t.b);
    }
    for (auto&& t: right_ops) {
      if (chmin(xr, t.a)) Rb.clear();
      if (xr == t.a) Rb.eb(t.b);
    }
    int Lm = mex(Lb), Rm = mex(Rb);
    if (xl < xr) {
      A a = A::simplest(xl, xr, Lm == 0, Rm == 0);
      return {true, T(a, 0)};
    }
    if (xl == xr) {
      if (Lm == Rm) return {true, T(xl, Lm)};
    }
    return {false, T(0, 0)};
  }

  string to_string() {
    string x = a.to_string();
    x += " + *";
    x += ::to_string(b);
    return x;
  }

  // L, R はそれぞれ自分手番のときに勝てるか？
  pair<bool, bool> outcome() {
    if (a > 0) return {1, 0};
    if (a < 0) return {0, 1};
    if (b == 0) return {0, 0};
    return {1, 1};
  }
};
#line 3 "game/solve_partizan_game.hpp"

// number, star でいい感じに計算できたときだけ成功
// 失敗したときは、empty map が返る
// ・states：興味のある state 全体
// ・get_options：pair<vc<STATE>, vc<STATE>>(STATE), left ops / right ops
// https://qoj.ac/contest/1828/problem/9567
template <typename STATE, typename F>
map<STATE, Number_And_Star> solve_partizan_game(const vector<STATE>& states, F get_options) {
  using X = Number_And_Star;
  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;
    auto [lop, rop] = get_options(s);
    for (auto&& t: lop) left.eb(dfs(dfs, t));
    for (auto&& t: rop) right.eb(dfs(dfs, t));
    auto [ok, t] = X::from_options(left, right);
    if (!success) return X{};
    if (!ok) {
      // print("FAILED");
      // print(s);
      // print("LEFT");
      // for (auto& t: lop) {
      //   X x = dfs(dfs, t);
      //   print(t, x.to_string());
      // }
      // print("RIGHT");
      // for (auto& t: rop) {
      //   X x = dfs(dfs, t);
      //   print(t, x.to_string());
      // }
      success = 0;
      return X();
    }
    MP[s] = t;
    return MP[s] = t;
  };

  for (auto&& s: states) dfs(dfs, s);
  if (!success) MP.clear();
  return MP;
}

Back to top page