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<State: Eq + Hash>,
63{
64    game: G,
65    number: HashMap<G::State, i64>,
66}
67
68impl<G> PartisanGameAnalyzer<G>
69where
70    G: PartisanGame<State: Eq + Hash + Clone>,
71{
72    pub fn new(game: G) -> Self {
73        Self {
74            game,
75            number: Default::default(),
76        }
77    }
78    pub fn eval(&mut self, s: &G::State) -> i64 {
79        if let Some(n) = self.number.get(s).cloned() {
80            n
81        } else {
82            let lmax = self
83                .game
84                .next_left(s)
85                .map(|ns| self.eval(&ns))
86                .fold(i64::MIN, Ord::max);
87            let rmin = self
88                .game
89                .next_right(s)
90                .map(|ns| self.eval(&ns))
91                .fold(i64::MAX, Ord::min);
92            let res = Self::simple_number(lmax, rmin);
93            self.number.insert(s.clone(), res);
94            res
95        }
96    }
97    fn simple_number(lmax: i64, rmin: i64) -> i64 {
98        const FIX: u32 = 50;
99        assert!(lmax < rmin);
100        assert!(lmax + 1 != rmin);
101        if lmax < 0 && 0 < rmin {
102            0
103        } else {
104            let c = 63 - ((rmin - 1) ^ lmax).leading_zeros();
105            if c <= FIX {
106                (rmin - 1) >> c << c
107            } else if lmax >= 0 {
108                ((lmax >> FIX) + 1) << FIX
109            } else {
110                (rmin - 1) >> FIX << FIX
111            }
112        }
113    }
114}
competitive/algorithm/partisan_game.rs

competitive/algorithm/
partisan_game.rs
