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" }) }