AtCoder Beginner Contest 310 D

https://atcoder.jp/contests/abc310/tasks/abc310_d

しらみつぶしすればよいです。選手を1から順にチームに配置しますが、左に空いているチームを作らないように配置します。ここで、チームの選手の集合をビットを使うと書きやすいです。

// Peaceful Teams
#![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);
type Graph = Vec<usize>;

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

fn create_graph(N: usize, edges: Vec<Edge>) -> Graph {
    let mut graph: Graph = (0..N).map(|_| 0).collect();
    for (u, v) in edges.into_iter() {
        graph[u] |= 1 << v;
        graph[v] |= 1 << u
    }
    graph
}


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

fn read_input() -> (usize, usize, Vec<Edge>) {
    let v = read_vec();
    let N: usize = v[0];
    let T: usize = v[1];
    let M: usize = v[2];
    let edges: Vec<Edge> = (0..M).map(|_| read_edge()).collect();
    (N, T, edges)
}

fn g(first: usize, last: usize, v: Vec<usize>, graph: &Graph) -> usize {
    if first == last {
        return if v.iter().all(|n| *n != 0) { 1 } else { 0 }
    }
    
    let mut c: usize = 0;
    for i in 0..v.len() {
        let n = v[i];
        if (n & graph[first]) != 0 {
            continue
        }
        let mut w = v.to_vec();
        w[i] |= 1 << first;
        c += g(first + 1, last, w, graph);
        if v[i] == 0 {
            break
        }
    }
    c
}

fn f(N: usize, T: usize, edges: Vec<Edge>) -> usize {
    let graph = create_graph(N, edges);
    let v = vec![0; T];
    g(0, N, v, &graph)
}

//////////////////// main ////////////////////

fn main() {
    let (N, T, edges) = read_input();
    println!("{}", f(N, T, edges))
}