AtCoder Beginner Contest 427 D

https://atcoder.jp/contests/abc427/tasks/abc427_d

Kが10以下なので、各ターンで各々のノードが必勝かどうかを調べます。後ろのターンから決めます。

// The Simple Game
#![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()
}


//////////////////// Graph ////////////////////

type Node = usize;

type Edge = (Node, Node);

fn read_edge() -> Edge {
    let v: Vec<Node> = read_vec();
    let (U, V) = (v[0]-1, v[1]-1);
    (U, V)
}

struct Graph {
    bs: Vec<bool>,
    g: Vec<Vec<Node>>
}

impl Graph {
    fn read(N: usize, M: usize) -> Graph {
        let mut bs: Vec<bool> = vec![true; N];
        let S: String = read();
        for (i, c) in S.chars().enumerate() {
            bs[i] = c == 'A'
        }
        let mut g: Vec<Vec<Node>> = vec![vec![]; N];
        for _ in 0..M {
            let (U, V) = read_edge();
            g[U].push(V)
        }
        Graph { bs, g }
    }
}


//////////////////// Test ////////////////////

struct Test {
    K: usize,
    graph: Graph
}

impl Test {
    fn num_nodes(&self) -> usize {
        self.graph.g.len()
    }
    
    fn read() -> Test {
        let v: Vec<usize> = read_vec();
        let (N, M, K) = (v[0], v[1], v[2]);
        let graph = Graph::read(N, M);
        Test { K, graph }
    }
}


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

type DP = Vec<bool>;

fn initialize_dp(test: &Test) -> DP {
    test.graph.bs.clone()
}

fn update_dp(test: &Test, b: bool, dp: DP) -> DP {
    let N = test.num_nodes();
    let mut new_dp: DP = vec![false; N];
    for u in 0..N {
        if b {  // Aliceの番
            new_dp[u] = test.graph.g[u].iter().any(|&v| dp[v])
        }
        else {
            new_dp[u] = test.graph.g[u].iter().all(|&v| dp[v])
        }
    }
    new_dp
}

fn F_each(test: Test) -> bool {
    let mut dp = initialize_dp(&test);
    for _ in 0..test.K {
        dp = update_dp(&test, false, dp);
        dp = update_dp(&test, true, dp)
    }
    dp[0]
}

fn F(T: usize) {
    for _ in 0..T {
        let test = Test::read();
        println!("{}", if F_each(test) { "Alice" } else { "Bob" })
    }
}

fn main() {
    let T: usize = read();
    F(T)
}