competitive/algorithm/
partisan_game.rs

1use std::{collections::HashMap, hash::Hash, marker::PhantomData};
2
3type Marker<T> = PhantomData<fn() -> T>;
4
5pub trait PartisanGame {
6    type State;
7    type LIter: Iterator<Item = Self::State>;
8    type RIter: Iterator<Item = Self::State>;
9    fn next_left(&mut self, s: &Self::State) -> Self::LIter;
10    fn next_right(&mut self, s: &Self::State) -> Self::RIter;
11}
12
13pub struct PartisanGamer<S, F, G, L, R>
14where
15    F: FnMut(&S) -> L,
16    L: Iterator<Item = S>,
17    G: FnMut(&S) -> R,
18    R: Iterator<Item = S>,
19{
20    f: F,
21    g: G,
22    _marker: Marker<(S, L, R)>,
23}
24
25impl<S, F, G, L, R> PartisanGamer<S, F, G, L, R>
26where
27    F: FnMut(&S) -> L,
28    L: Iterator<Item = S>,
29    G: FnMut(&S) -> R,
30    R: Iterator<Item = S>,
31{
32    pub fn new(f: F, g: G) -> Self {
33        Self {
34            f,
35            g,
36            _marker: PhantomData,
37        }
38    }
39}
40
41impl<S, F, G, L, R> PartisanGame for PartisanGamer<S, F, G, L, R>
42where
43    F: FnMut(&S) -> L,
44    L: Iterator<Item = S>,
45    G: FnMut(&S) -> R,
46    R: Iterator<Item = S>,
47{
48    type State = S;
49    type LIter = L;
50    type RIter = R;
51    fn next_left(&mut self, s: &Self::State) -> Self::LIter {
52        (self.f)(s)
53    }
54    fn next_right(&mut self, s: &Self::State) -> Self::RIter {
55        (self.g)(s)
56    }
57}
58
59#[derive(Debug, Clone)]
60pub struct PartisanGameAnalyzer<G>
61where
62    G: PartisanGame,
63    G::State: Eq + Hash,
64{
65    game: G,
66    number: HashMap<G::State, i64>,
67}
68
69impl<G> PartisanGameAnalyzer<G>
70where
71    G: PartisanGame,
72    G::State: Eq + Hash + Clone,
73{
74    pub fn new(game: G) -> Self {
75        Self {
76            game,
77            number: Default::default(),
78        }
79    }
80    pub fn eval(&mut self, s: &G::State) -> i64 {
81        if let Some(n) = self.number.get(s).cloned() {
82            n
83        } else {
84            let lmax = self
85                .game
86                .next_left(s)
87                .map(|ns| self.eval(&ns))
88                .fold(i64::MIN, Ord::max);
89            let rmin = self
90                .game
91                .next_right(s)
92                .map(|ns| self.eval(&ns))
93                .fold(i64::MAX, Ord::min);
94            let res = Self::simple_number(lmax, rmin);
95            self.number.insert(s.clone(), res);
96            res
97        }
98    }
99    fn simple_number(lmax: i64, rmin: i64) -> i64 {
100        const FIX: u32 = 50;
101        assert!(lmax < rmin);
102        assert!(lmax + 1 != rmin);
103        if lmax < 0 && 0 < rmin {
104            0
105        } else {
106            let c = 63 - ((rmin - 1) ^ lmax).leading_zeros();
107            if c <= FIX {
108                (rmin - 1) >> c << c
109            } else if lmax >= 0 {
110                ((lmax >> FIX) + 1) << FIX
111            } else {
112                (rmin - 1) >> FIX << FIX
113            }
114        }
115    }
116}
competitive/algorithm/partisan_game.rs

competitive/algorithm/
partisan_game.rs
