AtCoder Regular Contest 108 参加記
D - AB
Cが一見ややこしそうなのでDを見ると、DPで行けそうという第一感を得るので考えてみる。N=1000なのでO(N^2)のDPをやることを考えてみる。
- i文字目を見ている時に、(最後に見たAの場所, 最後に見たBの場所)をもつといけそう？→無理そう
愚直解を書いて実験してみると、次の3つのみになるということが分かる。
- 1
- フィボナッチ数のN項目
- 2^(N-3)
何もわからないがこれを出力するコードを提出するとAC（48:59）
const MOD: usize = 1e9 as usize + 7; fn main() { let (r, w) = (std::io::stdin(), std::io::stdout()); let mut sc = IO::new(r.lock(), w.lock()); let n: usize = sc.read(); let aa = sc.chars()[0]; let ab = sc.chars()[0]; let ba = sc.chars()[0]; let bb = sc.chars()[0]; let ans = match [aa, ab, ba, bb] { ['A', 'A', 'A', 'A'] => 1, ['B', 'A', 'A', 'A'] => fib(n), ['A', 'B', 'A', 'A'] => pow(n), ['B', 'B', 'A', 'A'] => pow(n), ['A', 'A', 'B', 'A'] => 1, ['B', 'A', 'B', 'A'] => pow(n), ['A', 'B', 'B', 'A'] => fib(n), ['B', 'B', 'B', 'A'] => fib(n), ['A', 'A', 'A', 'B'] => 1, ['B', 'A', 'A', 'B'] => fib(n), ['A', 'B', 'A', 'B'] => 1, ['B', 'B', 'A', 'B'] => 1, ['A', 'A', 'B', 'B'] => 1, ['B', 'A', 'B', 'B'] => pow(n), ['A', 'B', 'B', 'B'] => 1, ['B', 'B', 'B', 'B'] => 1, _ => unreachable!(), }; println!("{}", ans); // // for mask in 0..(1 << 5) { // let aa = if mask & (1 << 0) == 0 { 'A' } else { 'B' }; // let ab = if mask & (1 << 1) == 0 { 'A' } else { 'B' }; // let ba = if mask & (1 << 2) == 0 { 'A' } else { 'B' }; // let bb = if mask & (1 << 3) == 0 { 'A' } else { 'B' }; // // // println!("{:?}", [aa, ab, ba, bb]); // // let mut v = vec![vec!['A', 'B']]; // for i in 0..10 { // let mut next = vec![]; // for t in v { // for i in 1..t.len() { // let c = match (t[i - 1], t[i]) { // ('A', 'A') => aa, // ('A', 'B') => ab, // ('B', 'A') => ba, // ('B', 'B') => bb, // _ => unreachable!(), // }; // let mut x = t.clone(); // x.insert(i, c); // next.push(x); // } // } // v = next; // v.sort(); // v.dedup(); // // println!("n={} {}", i + 3, v.len()); // } // println!("{:?} {}", [aa, ab, ba, bb], v.len()); // } } fn fib(n: usize) -> usize { let mut prev = [1, 1]; for _ in 4..=n { let next = (prev[0] + prev[1]) % MOD; prev = [prev[1], next]; } prev[1] } fn pow(n: usize) -> usize { if n <= 3 { 1 } else { let mut res = 1; for _ in 0..(n - 3) { res = (res * 2) % MOD; } res } } pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>); impl<R: std::io::Read, W: std::io::Write> IO<R, W> { pub fn new(r: R, w: W) -> Self { Self(r, std::io::BufWriter::new(w)) } pub fn write<S: ToString>(&mut self, s: S) { use std::io::Write; self.1.write_all(s.to_string().as_bytes()).unwrap(); } pub fn read<T: std::str::FromStr>(&mut self) -> T { use std::io::Read; let buf = self .0 .by_ref() .bytes() .map(|b| b.unwrap()) .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t') .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t') .collect::<Vec<_>>(); unsafe { std::str::from_utf8_unchecked(&buf) } .parse() .ok() .expect("Parse error.") } pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> { (0..n).map(|_| self.read()).collect() } pub fn chars(&mut self) -> Vec<char> { self.read::<String>().chars().collect() } }
C - Keep Graph Connected
- 何も分からないが、連結になっていれば良いので木を作ることを考える。
- 「辺の両端の頂点に書き込まれた整数を x,y として、x,y のいずれか一方のみが辺についたラベルと等しい」となっているが、まず「いずれか一方のみ、または両方がラベルと等しい」木を作り、その頂点のラベルを適当に書き換えることで「一方のみ」のグラフにできる。
- BFS木を作りながら、新たに到達した頂点に、その頂点に到達する際に使った辺のラベルを書き込むと、先ほどの条件を満たすグラフができることに気付く。
これを実装するだけなのだが、バグらせまくって2WAしてAC（83:21 + 2WA）
use std::collections::{BTreeSet, VecDeque}; fn main() { let (r, w) = (std::io::stdin(), std::io::stdout()); let mut sc = IO::new(r.lock(), w.lock()); let n: usize = sc.read(); let m: usize = sc.read(); let mut graph = vec![vec![]; n]; for _ in 0..m { let u = sc.read::<usize>() - 1; let v = sc.read::<usize>() - 1; let c: usize = sc.read(); graph[u].push((v, c)); graph[v].push((u, c)); } let mut vis = vec![false; n]; let mut ans = vec![0; n]; vis[0] = true; let mut q = VecDeque::new(); q.push_back(0); let mut used = vec![BTreeSet::new(); n]; while let Some(v) = q.pop_front() { for &(next, label) in graph[v].iter() { if vis[next] { continue; } vis[next] = true; if ans[v] != label { ans[next] = label; } q.push_back(next); used[v].insert(label); used[next].insert(label); } } for i in 0..n { if ans[i] != 0 { continue; } ans[i] = (1..=n).find(|&x| !used[i].contains(&x)).unwrap(); } for i in 0..n { println!("{}", ans[i]); } } pub struct UnionFind { parent: Vec<usize>, sizes: Vec<usize>, size: usize, } impl UnionFind { pub fn new(n: usize) -> UnionFind { UnionFind { parent: (0..n).map(|i| i).collect::<Vec<usize>>(), sizes: vec![1; n], size: n, } } pub fn find(&mut self, x: usize) -> usize { if x == self.parent[x] { x } else { let px = self.parent[x]; self.parent[x] = self.find(px); self.parent[x] } } pub fn unite(&mut self, x: usize, y: usize) -> bool { let parent_x = self.find(x); let parent_y = self.find(y); if parent_x == parent_y { return false; } let (large, small) = if self.sizes[parent_x] < self.sizes[parent_y] { (parent_y, parent_x) } else { (parent_x, parent_y) }; self.parent[small] = large; self.sizes[large] += self.sizes[small]; self.sizes[small] = 0; self.size -= 1; true } } pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>); impl<R: std::io::Read, W: std::io::Write> IO<R, W> { pub fn new(r: R, w: W) -> Self { Self(r, std::io::BufWriter::new(w)) } pub fn write<S: ToString>(&mut self, s: S) { use std::io::Write; self.1.write_all(s.to_string().as_bytes()).unwrap(); } pub fn read<T: std::str::FromStr>(&mut self) -> T { use std::io::Read; let buf = self .0 .by_ref() .bytes() .map(|b| b.unwrap()) .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t') .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t') .collect::<Vec<_>>(); unsafe { std::str::from_utf8_unchecked(&buf) } .parse() .ok() .expect("Parse error.") } pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> { (0..n).map(|_| self.read()).collect() } pub fn chars(&mut self) -> Vec<char> { self.read::<String>().chars().collect() } }
結果
- 赤パフォ: ABCDE 94:10
- 橙パフォ: ABCD 61:21
- 2128: ABCD93:21
感想
- Dで速やかに実験に移行できたのは良かった（運も良かった）。
- Cでバグらせまくったのは良くなかった。特に、気づいていたケースをケアし忘れていたので、実装前に気づいた注意すべきことを提出前に確認できるように、リストアップしておいたほうが良いかもしれない。
