ABCDFの5完でした。これで冷えるのしょっぺぇ... # A - 22222 いい感じに`2`だけfilterすればOK。ワンライナーで書けて気持ちいです。[提出](https://atcoder.jp/contests/abc394/submissions/62993496) ```rust use itertools::Itertools; use proconio::{input, marker::Chars}; fn main() { input!{ s: Chars } println!("{}", s.iter().filter(|&c| c==&'2').join("")); } ``` # B - cat catコマンドみたいなことをします。長さをkeyとしてソートすればOK。これもワンライナーで書けて気持ちいです。[提出]() ```rust use itertools::Itertools; use proconio::{input, marker::Chars}; fn main() { input!{ n: usize, ss: [Chars; n], } println!("{}", ss.iter() .sorted_unstable_by_key(|s|s.len()) .map(|v|v.iter().join("")) .join("") ); } ``` # C - Debug `WWWA`があったとして、これを置換していくと`WWAC`, `WACC`, `ACCC`のように、順に左へと伝播していきます。よって、前から順に見ていって、WAを見つけたらそこから`W`である間後ろへ置換していく、といったコードでACを得ることができます。一度後ろまで戻って置換を終えたブロックはそれ以上置換されないことを考えると、書く文字が読まれる回数はたかだか2回であり、$S$の文字列長を$|S|$とすると$O(|S|)$でこの問題が解けます。[提出](https://atcoder.jp/contests/abc394/submissions/63009833) ```rust use itertools::Itertools; use proconio::{input, marker::Chars}; fn main() { input!{ mut s: Chars, } let n = s.len(); for i in 0..n-1 { if s[i] == 'W' && s[i+1] == 'A' { let mut last_found = i; for j in (0..=i).rev() { if s[j] != 'W' { break; } last_found = j; s[j] = 'C'; } s[last_found] = 'A'; s[i+1] = 'C'; } } println!("{}", s.iter().join("")); } ``` # D - Colorful Bracket Sequence 括弧列典型です。「正しい括弧列」を判定したいとき、開括弧のときはスタックへと加えて、閉じ括弧のときはスタックの最も上の文字が対応する開括弧のときはそれをpop、そうでなければ閉じ括弧をstackへ加えます。全ての操作を終えたとき、スタックが空であれば「正しい括弧列」であると判定できます。この問題では複数の括弧がありますが、同様の方法でACすることができます。[提出](https://atcoder.jp/contests/abc394/submissions/63017979) ```rust use proconio::{input, marker::Chars}; fn main() { input!{ s: Chars, } let mut stk = vec![]; for &c in s.iter() { if c == '(' || c == '[' || c == '<' { stk.push(c); } else { if let Some(pair) = stk.pop() { match c { ']' => { if pair != '[' { println!("No"); return; } } ')' => { if pair != '(' { println!("No"); return; } } '>' => { if pair != '<' { println!("No"); return; } } _ => unreachable!() } } else { println!("No"); return; } } } println!("{}", if stk.is_empty() { "Yes" } else { "No" }); } ``` 確かに知ってさえいれば簡単な典型ですが、昔に類題が出たときは茶色diffだった記憶があるので灰diffまで落ちるのか...と少し驚きです。 # F - Alkane ある頂点を根とするアルカンを構築したときに構築可能な最大の大きさはDFSによって求めることができます。これは、ある頂点からは葉の方向に3つ分の辺を選ぶことができますが、そのうち大きい方から3つを取れば良いことから、DFSの帰りがけ時に部分アルカンの最大の大きさを求めることができるからです。 1つの頂点を根とするアルカンの最大サイズを求めましたが、このまま$N$頂点に対して同じことを行うと$O(N^2)$となり間に合いません。ここで、差分を取りながら計算をする全方位木DPに持ち込むことによって、全体で$O(N)$とすることができます。ある頂点を根とする有向DFS木を構築して、頂点を移動する際にその向きの有向辺を付け加えるイメージです。詳しくは実装を見ればわかりやすいと思います。[提出](https://atcoder.jp/contests/abc394/submissions/63059801) ```rust use std::cmp::Reverse; use itertools::Itertools; use proconio::{input, marker::Usize1}; fn dfs(g: &Vec>, p: usize, dp: &mut Vec>, seen: &mut Vec) -> u64 { seen[p] = true; for &ni in g[p].iter() { if seen[ni] { continue; } let res = dfs(g, ni, dp, seen); dp[p].push((ni, res)); } while dp[p].len() < 6 { dp[p].push((!0, 1)); } dp[p].iter().sorted_unstable_by_key(|xi| Reverse(xi.1)).take(3).map(|xi| xi.1).sum::()+1 } fn dfs2(p: usize, dp: &mut Vec>, seen: &mut Vec) -> u64 { seen[p] = true; let mut res = dp[p].iter().sorted_unstable_by_key(|xi| Reverse(xi.1)).take(4).map(|xi| xi.1).sum::()+1; for i in 0..dp[p].len() { let (ni, c) = dp[p][i]; if ni == !0 || seen[ni] { continue; } let n_cost = dp[p].iter() .filter(|xi| xi.0 != ni) .sorted_unstable_by_key(|xi| Reverse(xi.1)) .map(|xi| xi.1) .take(3) .sum::(); dp[ni].push((!0, n_cost)); let res2 = dfs2(ni, dp, seen); res = res.max(res2); } res } fn main() { input!{ n: usize, e: [(Usize1, Usize1); n-1], } let g = e.iter() .fold(vec![vec![]; n], |mut g, &(u, v)| { g[u].push(v); g[v].push(u); g }); let n_g = e.iter() .fold(vec![vec![]; n], |mut n_g, &(u, v)| { if g[u].len() >= 4 && g[v].len() >= 4 { n_g[u].push(v); n_g[v].push(u); } n_g }); let mut checked = vec![false; n]; let mut checked2 = vec![false; n]; let mut dp = vec![vec![]; n]; let mut ans = -1i64; for i in 0..n { if g[i].len() < 4 || checked[i] { continue; } dfs(&n_g, i, &mut dp, &mut checked); let size = dfs2(i, &mut dp, &mut checked2); ans.chmax(size as i64); } println!("{}", ans); } ``` # E - Palindromic Shortest Path(Upsolve) 分からず。[[ABC394E - Palindromic Shortest Path]]にまとめたので、よければぜひ。[提出](https://atcoder.jp/contests/abc394/submissions/63068955) ```rust use std::collections::VecDeque; use itertools::Itertools; use proconio::{input, marker::Chars}; fn main() { input!{ n: usize, c: [Chars; n], } let mut seen = vec![vec![INF; n]; n]; let mut que = VecDeque::new(); for i in 0..n { seen[i][i] = 0; que.push_back((i, i)); } for i in 0..n { for j in 0..n { if i == j { continue; } if c[i][j] != '-' { seen[i][j] = 1; que.push_back((i, j)); } } } while let Some((pi, pj)) = que.pop_front() { for ni in 0..n { for nj in 0..n { if c[ni][pi] == c[pj][nj] && c[ni][pi] != '-' && seen[ni][nj] == INF { seen[ni][nj] = seen[pi][pj] + 2; que.push_back((ni, nj)); } } } } println!("{}", seen.iter().map(|v| v.iter().map(|vi| if vi == &INF { -1 } else { *vi as i64 }).join(" ")).join(" ")); } ```