AtCoder Beginner Contest 349 E

https://atcoder.jp/contests/abc349/tasks/abc349_e

状態数がしかなくて、深さも9しかないので、ふつうにメモ化すればよいです。

// Weighted Tic-Tac-Toe
#![allow(non_snake_case)]


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}


//////////////////// Color ////////////////////

#[derive(PartialEq, Copy, Clone)]
enum Color {
    White = 0,
    Red = 1,
    Blue = 2
}

impl Color {
    fn from_u32(n: u32) -> Color {
        match n {
            0 => Color::White,
            1 => Color::Red,
            _ => Color::Blue
        }
    }
}


//////////////////// State ////////////////////

struct State {
    C: [[Color; 3]; 3]
}

impl State {
    fn clone(&self) -> State {
        State { C: self.C.clone() }
    }
    
    fn exists_line(&self, color: Color) -> bool {
        for i in 0..3 {
            if (0..3).all(|j| self.C[i][j] == color) {
                return true
            }
        }
        for j in 0..3 {
            if (0..3).all(|i| self.C[i][j] == color) {
                return true
            }
        }
        if (0..3).all(|i| self.C[i][i] == color) {
            true
        }
        else if (0..3).all(|i| self.C[i][2-i] == color) {
            true
        }
        else {
            false
        }
    }
    
    fn wins_red(&self) -> bool {
        self.exists_line(Color::Red)
    }
    
    fn wins_blue(&self) -> bool {
        self.exists_line(Color::Blue)
    }
    
    fn num_remained_cells(&self) -> usize {
        self.C.iter().flatten().filter(|&c| *c == Color::White).count()
    }
    
    fn is_finished(&self) -> bool {
        self.num_remained_cells() == 0
    }
    
    fn turn(&self) -> Color {
        let n = self.num_remained_cells();
        if n % 2 == 1 { Color::Red } else { Color::Blue }
    }
    
    fn encode(&self) -> u32 {
        let mut s: u32 = 0;
        for i in (0..3).rev() {
            for j in (0..3).rev() {
                s = s * 3 + (self.C[i][j] as u32)
            }
        }
        s
    }
    
    fn decode(mut s: u32) -> State {
        let mut C: [[Color; 3]; 3] = [[Color::White; 3]; 3];
        for i in 0..3 {
            for j in 0..3 {
                C[i][j] = Color::from_u32(s % 3);
                s /= 3
            }
        }
        State { C }
    }
    
    fn nexts(&self) -> Vec<u32> {
        let mut states: Vec<u32> = vec![];
        let color = self.turn();
        for i in 0..3 {
            for j in 0..3 {
                if self.C[i][j] == Color::White {
                    let mut s = self.clone();
                    s.C[i][j] = color;
                    states.push(s.encode())
                }
            }
        }
        states
    }
}


//////////////////// Board ////////////////////

struct Board {
    A: [[i64; 3]; 3],
    win_vec: Vec<i32>
}

impl Board {
    fn wins_core(&mut self, s: u32) -> bool {
        let state = State::decode(s);
        if state.wins_red() {
            true
        }
        else if state.wins_blue() {
            false
        }
        else if state.is_finished() {
            let mut sum_red: i64 = 0;
            let mut sum_blue: i64 = 0;
            for i in 0..3 {
                for j in 0..3 {
                    if state.C[i][j] == Color::Red {
                        sum_red += self.A[i][j]
                    }
                    else {
                        sum_blue += self.A[i][j]
                    }
                }
            }
            sum_red > sum_blue
        }
        else if state.turn() == Color::Red {
            state.nexts().into_iter().any(|s1| self.wins(s1))
        }
        else {
            !state.nexts().into_iter().any(|s1| !self.wins(s1))
        }
    }
    
    fn wins(&mut self, s: u32) -> bool {
        if self.win_vec[s as usize] == 0 {
            let b = self.wins_core(s);
            self.win_vec[s as usize] = if b { 1 } else { 2 }
        }
        self.win_vec[s as usize] == 1
    }
    
    fn read_row() -> [i64; 3] {
        let v: Vec<i64> = read_vec();
        [v[0], v[1], v[2]]
    }
    
    fn read() -> Board {
        let A: [[i64; 3]; 3] = [Board::read_row(),
                                Board::read_row(),
                                Board::read_row()];
        let N = 3usize.pow(9);
        let win_vec: Vec<i32> = vec![0; N];
        Board { A, win_vec }
    }
}


//////////////////// process ////////////////////

fn F(mut board: Board) -> bool {
    board.wins(0)
}

fn main() {
    let board = Board::read();
    let b = F(board);
    println!("{}", if b { "Takahashi" } else { "Aoki" })
}