https://atcoder.jp/contests/abc354/tasks/abc354_e
特に工夫もせずにグラフを作ります。それで十分間に合いました。
// Remove Pairs #![allow(non_snake_case)] use std::collections::HashMap; //////////////////// 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); struct Graph { g: Vec<usize> } impl Graph { fn len(&self) -> usize { self.g.len() } fn edges(&self) -> Vec<Edge> { let mut edges: Vec<Edge> = vec![]; for u in 0..self.len() { if self.g[u] == 0 { continue } for v in u+1..self.len() { if ((self.g[u] >> v) & 1) != 0 { edges.push((u, v)) } } } edges } fn is_isolated(&self) -> bool { self.g.iter().all(|&s| s == 0) } fn remove_node(&mut self, v: Node) -> usize { let s = self.g[v]; for i in 0..self.len() { if ((s >> i) & 1) == 1 { self.g[i] -= 1 << v; } } self.g[v] = 0; s } fn resume(&mut self, v: Node, s: usize) { for i in 0..self.len() { if ((s >> i) & 1) == 1 { self.g[i] |= 1 << v } } self.g[v] = s } } //////////////////// process //////////////////// type Card = (i32, i32); fn read_card() -> Card { let v = read_vec(); let (A, B) = (v[0], v[1]); (A, B) } fn read_input() -> Vec<Card> { let N = read(); let cards: Vec<Card> = (0..N).map(|_| read_card()).collect(); cards } fn add_edges(map: HashMap<i32, usize>, g: &mut Vec<usize>) { let N = g.len(); for (_, s) in map.into_iter() { for i in 0..N { if ((s >> i) & 1) == 0 { continue } for j in 0..N { if i != j && ((s >> j) & 1) == 1 { g[i] |= 1 << j } } } } } fn make_graph(cards: Vec<Card>) -> Graph { let N = cards.len(); let mut map1: HashMap<i32, usize> = HashMap::new(); let mut map2: HashMap<i32, usize> = HashMap::new(); for (i, (A, B)) in cards.into_iter().enumerate() { let e1 = map1.entry(A).or_insert(0); *e1 |= 1 << i; let e2 = map2.entry(B).or_insert(0); *e2 |= 1 << i } let mut g: Vec<usize> = vec![0; N]; add_edges(map1, &mut g); add_edges(map2, &mut g); Graph { g } } fn wins(s: usize, graph: &mut Graph, memo: &mut HashMap<usize, bool>) -> bool { if let Some(b) = memo.get(&s) { *b } else if graph.is_isolated() { false } else { for (u, v) in graph.edges().into_iter() { let su = graph.remove_node(u); let sv = graph.remove_node(v); let s1 = s - (1 << u) - (1 << v); let b1 = wins(s1, graph, memo); graph.resume(v, sv); graph.resume(u, su); if !b1 { memo.insert(s, true); return true } } memo.insert(s, false); false } } fn F(cards: Vec<Card>) -> bool { let N = cards.len(); let mut graph = make_graph(cards); let mut memo: HashMap<usize, bool> = HashMap::new(); wins((1 << N) - 1, &mut graph, &mut memo) } fn main() { let cards = read_input(); println!("{}", (if F(cards) { "Takahashi" } else { "Aoki" }).to_string()); }
