AtCoder Beginner Contest 305
AtCoder Beginner Contest 305 です。
A - Water Station
5で割った切り上げ・切り捨てを計算して、5をかけると前後の補給所の場所が分かるので、それのうち近い方を出力する。
fn main() { input! { n: usize, } let a1 = (n + 4) / 5 * 5; let a2 = n / 5 * 5; let f = |a:usize,b:usize| { a.max(b) - a.min(b) }; if f(a1, n) < f(a2, n) { println!("{}", a1); } else { println!("{}", a2); } }
B - ABCDEFG
A,B,C,D,E,F,G の間の距離が分かっているので、与えられている2つのアルファベットの距離を求める問題。 適当にそれぞれの位置を入れておいて引けば良い。
fn main() { input! { p : char, q : char, } let d = vec![0, 3, 4, 8, 9, 14, 23]; let i = (p as u8 - b'A') as usize; let j = (q as u8 - b'A') as usize; println!("{}", d[i.max(j)] - d[i.min(j)]); }
C - Snuke the Cookie Picker
長方形になるようにクッキーが置かれていて、1個なくなっているクッキーの場所を求める問題。$2 \times 2$ 以上なので、最小・最大の座標を求めておけば長方形の4つ端が分かるので、その間でクッキーが置かれていないところが答え。
fn main() { input! { h : usize, w : usize, s : [Chars; h] } let mut minx = 1000; let mut miny = 1000; let mut maxx = 0; let mut maxy = 0; for i in 0..h { for j in 0..w { if s[i][j] == '#' { minx = minx.min(i); miny = miny.min(j); maxx = maxx.max(i); maxy = maxy.max(j); } }} let mut ans = (0,0); for i in minx..=maxx { for j in miny..=maxy { if s[i][j] == '.' { ans = (i,j); } }} println!("{} {}", ans.0+1, ans.1+1) }
提出
D - Sleep Log
累積和で大まかに求めておく。累積和で求められなかったはみ出ている分を後出て足してあげる。
fn main() { input! { n : usize, a : [usize; n], q : usize, queries : [(usize, usize); q] } let mut b = vec![0; n - 1]; for i in 0..n-1 { if i % 2 == 1 { b[i] = a[i+1] - a[i]; } } let mut csum = vec![0; n]; for i in 0..n-1 { csum[i+1] = csum[i] + b[i]; } for (l, r) in queries { let lindex = a.lower_bound(&l); let rindex = a.upper_bound(&r); let mut ans = csum[rindex - 1] - csum[lindex]; if lindex % 2 == 0 { ans += a[lindex] - l; } if rindex % 2 == 0 { ans += r - a[rindex - 1]; } println!("{}", ans); } }
E - Art Gallery on Graph
なんか沼った。最初の提出に$=$ が 抜けているだけだった。
グラフ上に警備員がいて、それぞれ体力が決まっていて、体力分離れたところまで警備できる。 警備されている頂点を昇順に出力して下さいという問題。
スタート地点をいくつか持って、最大値から更新していくダイクストラをすると良い。
fn main() { input! { n : usize, m : usize, k : usize, edges : [(Usize1, Usize1); m], ph : [(Usize1, usize); k] } let mut g = vec![vec![]; n]; for (a, b) in edges { g[a].push(b); g[b].push(a); } let mut que = BinaryHeap::new(); let mut dist = vec![None; n]; for (p, h) in ph { que.push((h, p)); dist[p] = Some(h); } while let Some((h, p)) = que.pop() { if dist[p].unwrap() != h { continue; } if h == 0 { continue; } for &q in &g[p] { if dist[q].is_none() || dist[q].unwrap_or(0) < h - 1 { dist[q] = Some(h - 1); que.push((h - 1, q)); } } } let ans = (0..n).filter(|&i| dist[i].is_some()).collect_vec(); println!("{}\n{}", ans.len(), ans.iter().map(|a| a + 1).join(" ")); }
F - Dungeon Explore
入力がめんどくさいインタラクティブ。 Rust のインタラクティブが下手くそ過ぎて TLE めっちゃ出しちゃった。 最初から自作の適宜入力取るやつで書いておけば良かった。
移動回数 $ 2 \times N $ 以下で頂点$1$ から頂点$N$ に移動してくださいという問題。 連結かつ単純なので、DFSみたいに探索していったら $2 \times N$ 回以内に $N$ まで移動できる。
fn main() { let (n, m) : (usize, usize) = input_t(); let mut g = vec![vec![]; n]; let mut used = vec![false; n]; let mut stack= vec![]; let mut pref = vec![0; n]; let e = input_vec::<usize>().into_iter().skip(1).map(|x| x - 1).collect_vec(); g[0] = e; for &u in &g[0] { stack.push((false, u)); stack.push((true, u)); pref[u] = 0; } while let Some((f, v)) = stack.pop() { if f { if used[v] { continue; } used[v] = true; println!("{} ", v + 1); if v + 1 == n { break; } stdout().flush().unwrap(); let e = input_vec::<usize>().into_iter().skip(1).map(|x| x - 1).collect_vec(); g[v] = e; for &u in &g[v] { if used[u] { continue; } stack.push((false, u)); stack.push((true, u)); pref[u] = v; } } else { println!("{} ", pref[v] + 1); stdout().flush().unwrap(); let _ = input_vec::<usize>().into_iter().skip(1).map(|x| x - 1).collect_vec(); } } }
G - Banned Substrings
圧倒的に時間が足りなかった。
$N$ がある程度小さい場合は、末尾6桁を持って DP したら答えを求めることができる。しかし、大きいので DP 遷移を 行列にして行列累乗をしたら良い。 6桁未満は愚直に求めると楽かも。
うーん…解きたかった。
fn main() { input! { n : usize, m : usize, s : [String; m] } let mut dp = FxHashMap::default(); dp.insert("".to_owned(), Mint::new(1)); for _ in 0..n.min(6) { let mut next = FxHashMap::default(); for (k, &v) in dp.iter() { for i in 0..2 { let k = k.chars().rev().take(5).collect::<String>(); let k = k.chars().rev().collect::<String>(); let ns = k + if i==0 { "a" } else { "b" }; if s.iter().any(|s| { let ns = ns.chars().rev().take(s.len()).collect::<String>(); let ns = ns.chars().rev().collect::<String>(); &ns == s }) { continue; } *next.entry(ns).or_insert(Mint::new(0)) += v; } } dp = next; } if n <= 6 { println!("{}", dp.iter().fold(Mint::new(0), |acc, (_, x)| acc + x)); return; } let mut v = vec![Mint::new(0); 1<<6]; let mut mat = matrix::Matrix::new(1<<6, 1<<6, Mint::new(0)); for (k, &val) in dp.iter() { let k = k.chars().fold(0, |acc, c| acc * 2 + if c=='a' { 0 } else { 1 }); v[k] += val; for i in 0..2 { let l = (k * 2 + i) & 0b111111; mat[k][l] += 1; } } let t = mat.pow(n - 6, Mint::new(1)); let ans = t * &v; println!("{}", ans.iter().sum::<Mint>()); }
Ex - Shojin
見てない
まとめ
途中の問題で沼り過ぎて、勝負のGにあんまり時間かけられなかった…。 競プロやらなさすぎて、鈍ってるなぁと思った。
パフォーマンス 1469。レート 1702 → 1680