Dyadic rational number （2進有理数）
(number/dyadic_rational.hpp)

View this file on GitHub
Last update: 2022-01-30 12:05:36+09:00
Include: #include "number/dyadic_rational.hpp"
Link: https://atcoder.jp/contests/abc229/submissions/28887690

2進有理数 (dyadic rational number) の実装 DyadicRational<Int, Uint = unsigned long long> ，また 2進有理数 $l, r$ によって定まる区間 $[l, r]$ に対する最簡数 (simplest number) $\{ l \mid r \}$ の計算．

2進有理数はその名の通り分母が二冪の有理数である．プログラミングコンテストでは組合せゲーム理論での応用例がある．

Int が整数部分を表すための符号付整数型で int や long long の利用を想定，Uint が小数部分を表すための符号なし整数型で unsigned や unsigned long long の利用を想定（__uint128_t も動くかもしれない）．メンバ変数 integ, frac がそれぞれ整数部分と小数部分に対応し，

$\displaystyle x = \mathrm{integ} + \frac{\mathrm{frac}}{2^\mathrm{FracLen}}$

がこのクラスのインスタンスが表す有理数 $x$ である．実装の制約上分母のオーダーは（Uint = unsigned long long の場合） $2^{63}$ が上限となる．

組合せゲームの2進有理数による評価

以下のすべての条件を満たす非不偏ゲーム (partizan game) は2進有理数を用いて局面の評価が可能．

有限個の手
有限で終了
「必ず先手が勝つ」（帰結類が $\mathscr{N}$ ）局面が存在しない

ゲームが DAG として表される場合，各局面の評価値を「その局面から先手が指した任意の局面の評価値の最大値と後手が指した任意の局面の評価値の最小値」の最簡数として再帰的に定める．この評価関数は直感的には先手の優勢度を示している．

複数の局面の直和に対する評価値は，各局面の評価値の和となる．

使用方法

`DyadicRational<Int>(Int x)`

コンストラクタ．整数 x に対応する元を生成する．

`double to_double()`

インスタンスが表す2進有理数を double 型の浮動小数点数に変換．

`DyadicRational<Int> right()`

インスタンスが表す2進有理数について， Surreal number （超現実数）の構成過程を表す木における右の子の値を返す．

`DyadicRational<Int> left()`

right() とは逆に，現在の値の左側の子の値を返す．

`DyadicRational<Int> DyadicRational<Int>::surreal(DyadicRational<Int> l, DyadicRational<Int> r)`

$l < r$ を満たす二進分数 $l$ , $r$ の最簡数 $\{ l \mid r \}$ ，すなわち $l < x < r$ を満たし surreal number の構成過程を表す木で根（ $0$ ）に最も近い要素の値を返す． $l < r$ を満たさない場合 runtime error となる．

現在は根から一歩ずつ right() または left() で探索していく実装になっているが，場合分けと bit 演算を頑張れば $O(1)$ になると思われる．

問題例

AOJ 1377: Black and White Boxes Blue-Red Hackenbush を含む．
技術室奥プログラミングコンテスト#6 Day1 P - Game on Colored Tree Blue-Red Hackenbush そのもの．
AtCoder Beginner Contest 229 H - Advance or Eat 帰結類 $\mathscr{N}$ に属する局面が存在しないゲームのため，2進有理数による解析が可能．

参考文献・リンク

安福・坂井・末續『組合せゲーム理論の世界: 数学で解き明かす必勝法』共立出版 2024.
組合せゲーム理論入門(1) 組合せゲーム理論の観点からの解説．
解説 - NECプログラミングコンテスト2021(AtCoder Beginner Contest 229) 非不偏ゲーム（Partisan Game）の問題例とその解き方．
- 提出 #27486895 - NECプログラミングコンテスト2021(AtCoder Beginner Contest 229) Nyaan さんの実装．

Code

#include <cassert>
#include <limits>
#include <type_traits>

// Dyadic rational, surreal numbers （超現実数）
// https://atcoder.jp/contests/abc229/submissions/28887690
template <class Int, class Uint = unsigned long long> struct DyadicRational {
    Int integ; // 整数部分
    Uint frac; // 小数部分の分子

    static constexpr int FracLen = std::numeric_limits<Uint>::digits - 1; // 2^63
    static constexpr Uint denom = Uint(1) << FracLen;                     // 小数部分の分母

    DyadicRational(Int x = 0) : integ(x), frac(0) {
        static_assert(
            0 < FracLen and FracLen < std::numeric_limits<Uint>::digits, "FracLen value error");
        static_assert(std::is_signed<Int>::value == true, "Int must be signed");
    }
    static DyadicRational _construct(Int x, Uint frac_) {
        DyadicRational ret(x);
        ret.frac = frac_;
        return ret;
    }
    double to_double() const { return integ + double(frac) / denom; }

    // static DyadicRational from_rational(Int num, int lg_den);
    bool operator==(const DyadicRational &r) const { return integ == r.integ and frac == r.frac; }
    bool operator!=(const DyadicRational &r) const { return integ != r.integ or frac != r.frac; }
    bool operator<(const DyadicRational &r) const {
        return integ != r.integ ? integ < r.integ : frac < r.frac;
    }
    bool operator<=(const DyadicRational &r) const { return (*this == r) or (*this < r); }
    bool operator>(const DyadicRational &r) const { return r < *this; }
    bool operator>=(const DyadicRational &r) const { return r <= *this; }

    DyadicRational operator+(const DyadicRational &r) const {
        auto i = integ + r.integ;
        auto f = frac + r.frac;
        if (f >= denom) ++i, f -= denom; // overflow
        return DyadicRational::_construct(i, f);
    }
    DyadicRational operator-(const DyadicRational &r) const {
        auto i = integ - r.integ;
        auto f = frac - r.frac;
        if (f > denom) --i, f += denom; // overflow
        return DyadicRational::_construct(i, f);
    }
    DyadicRational operator-() const { return DyadicRational() - *this; }
    DyadicRational &operator+=(const DyadicRational &r) { return *this = *this + r; }

    DyadicRational right() const {
        if (frac == 0) {
            if (integ >= 0) {
                return DyadicRational(integ + 1);
            } else {
                return DyadicRational::_construct(integ, Uint(1) << (FracLen - 1));
            }
        }
        int d = __builtin_ctzll(frac);
        return DyadicRational::_construct(integ, frac ^ (Uint(1) << (d - 1)));
    }
    DyadicRational left() const {
        if (frac == 0) {
            if (integ <= 0) {
                return DyadicRational(integ - 1);
            } else {
                return DyadicRational::_construct(integ - 1, Uint(1) << (FracLen - 1));
            }
        }
        int d = __builtin_ctzll(frac);
        return DyadicRational::_construct(integ, frac ^ (Uint(3) << (d - 1)));
    }

    // Surreal number { l | r }
    static DyadicRational surreal(const DyadicRational &l, const DyadicRational &r) {
        assert(l < r);
        DyadicRational x(0);
        if (l.integ > 0) x = DyadicRational(l.integ);
        if (r.integ < 0) x = DyadicRational(r.integ);
        while (true) {
            if (x <= l) {
                x = x.right();
            } else if (x >= r) {
                x = x.left();
            } else {
                break;
            }
        }
        return x;
    }
    template <class OStream> friend OStream &operator<<(OStream &os, const DyadicRational &x) {
        return os << x.to_double();
    }
};
// using dyrational = DyadicRational<long long>;

#line 1 "number/dyadic_rational.hpp"
#include <cassert>
#include <limits>
#include <type_traits>

// Dyadic rational, surreal numbers （超現実数）
// https://atcoder.jp/contests/abc229/submissions/28887690
template <class Int, class Uint = unsigned long long> struct DyadicRational {
    Int integ; // 整数部分
    Uint frac; // 小数部分の分子

    static constexpr int FracLen = std::numeric_limits<Uint>::digits - 1; // 2^63
    static constexpr Uint denom = Uint(1) << FracLen;                     // 小数部分の分母

    DyadicRational(Int x = 0) : integ(x), frac(0) {
        static_assert(
            0 < FracLen and FracLen < std::numeric_limits<Uint>::digits, "FracLen value error");
        static_assert(std::is_signed<Int>::value == true, "Int must be signed");
    }
    static DyadicRational _construct(Int x, Uint frac_) {
        DyadicRational ret(x);
        ret.frac = frac_;
        return ret;
    }
    double to_double() const { return integ + double(frac) / denom; }

    // static DyadicRational from_rational(Int num, int lg_den);
    bool operator==(const DyadicRational &r) const { return integ == r.integ and frac == r.frac; }
    bool operator!=(const DyadicRational &r) const { return integ != r.integ or frac != r.frac; }
    bool operator<(const DyadicRational &r) const {
        return integ != r.integ ? integ < r.integ : frac < r.frac;
    }
    bool operator<=(const DyadicRational &r) const { return (*this == r) or (*this < r); }
    bool operator>(const DyadicRational &r) const { return r < *this; }
    bool operator>=(const DyadicRational &r) const { return r <= *this; }

    DyadicRational operator+(const DyadicRational &r) const {
        auto i = integ + r.integ;
        auto f = frac + r.frac;
        if (f >= denom) ++i, f -= denom; // overflow
        return DyadicRational::_construct(i, f);
    }
    DyadicRational operator-(const DyadicRational &r) const {
        auto i = integ - r.integ;
        auto f = frac - r.frac;
        if (f > denom) --i, f += denom; // overflow
        return DyadicRational::_construct(i, f);
    }
    DyadicRational operator-() const { return DyadicRational() - *this; }
    DyadicRational &operator+=(const DyadicRational &r) { return *this = *this + r; }

    DyadicRational right() const {
        if (frac == 0) {
            if (integ >= 0) {
                return DyadicRational(integ + 1);
            } else {
                return DyadicRational::_construct(integ, Uint(1) << (FracLen - 1));
            }
        }
        int d = __builtin_ctzll(frac);
        return DyadicRational::_construct(integ, frac ^ (Uint(1) << (d - 1)));
    }
    DyadicRational left() const {
        if (frac == 0) {
            if (integ <= 0) {
                return DyadicRational(integ - 1);
            } else {
                return DyadicRational::_construct(integ - 1, Uint(1) << (FracLen - 1));
            }
        }
        int d = __builtin_ctzll(frac);
        return DyadicRational::_construct(integ, frac ^ (Uint(3) << (d - 1)));
    }

    // Surreal number { l | r }
    static DyadicRational surreal(const DyadicRational &l, const DyadicRational &r) {
        assert(l < r);
        DyadicRational x(0);
        if (l.integ > 0) x = DyadicRational(l.integ);
        if (r.integ < 0) x = DyadicRational(r.integ);
        while (true) {
            if (x <= l) {
                x = x.right();
            } else if (x >= r) {
                x = x.left();
            } else {
                break;
            }
        }
        return x;
    }
    template <class OStream> friend OStream &operator<<(OStream &os, const DyadicRational &x) {
        return os << x.to_double();
    }
};
// using dyrational = DyadicRational<long long>;

Dyadic rational number （2進有理数） (number/dyadic_rational.hpp)

組合せゲームの2進有理数による評価

使用方法

DyadicRational<Int>(Int x)

double to_double()

DyadicRational<Int> right()

DyadicRational<Int> left()

DyadicRational<Int> DyadicRational<Int>::surreal(DyadicRational<Int> l, DyadicRational<Int> r)

問題例