ABCDFの5完でした。これで冷えるのしょっぺぇ...
いい感じに
2
だけfilterすればOK。ワンライナーで書けて気持ちいです。
提出
use itertools::Itertools;
use proconio::{input, marker::Chars};
fn main() {
input!{
s: Chars
}
println!("{}", s.iter().filter(|&c| c==&'2').join(""));
}catコマンドみたいなことをします。長さをkeyとしてソートすればOK。これもワンライナーで書けて気持ちいです。 提出
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("")
);
}WWWA
があったとして、これを置換していくと
WWAC
,
WACC
,
ACCC
のように、順に左へと伝播していきます。よって、前から順に見ていって、WAを見つけたらそこから
W
である間後ろへ置換していく、といったコードでACを得ることができます。
一度後ろまで戻って置換を終えたブロックはそれ以上置換されないことを考えると、書く文字が読まれる回数はたかだか2回であり、
\(S\)
の文字列長を
\(|S|\)
とすると
\(O(|S|)\)
でこの問題が解けます。
提出
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(""));
}
括弧列典型です。「正しい括弧列」を判定したいとき、開括弧のときはスタックへと加えて、閉じ括弧のときはスタックの最も上の文字が対応する開括弧のときはそれをpop、そうでなければ閉じ括弧をstackへ加えます。全ての操作を終えたとき、スタックが空であれば「正しい括弧列」であると判定できます。
この問題では複数の括弧がありますが、同様の方法でACすることができます。
提出
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まで落ちるのか...と少し驚きです。
ある頂点を根とするアルカンを構築したときに構築可能な最大の大きさはDFSによって求めることができます。これは、ある頂点からは葉の方向に3つ分の辺を選ぶことができますが、そのうち大きい方から3つを取れば良いことから、DFSの帰りがけ時に部分アルカンの最大の大きさを求めることができるからです。
1つの頂点を根とするアルカンの最大サイズを求めましたが、このまま
\(N\)
頂点に対して同じことを行うと
\(O(N^2)\)
となり間に合いません。
ここで、差分を取りながら計算をする全方位木DPに持ち込むことによって、全体で
\(O(N)\)
とすることができます。ある頂点を根とする有向DFS木を構築して、頂点を移動する際にその向きの有向辺を付け加えるイメージです。詳しくは実装を見ればわかりやすいと思います。
提出
use std::cmp::Reverse;
use itertools::Itertools;
use proconio::{input, marker::Usize1};
fn dfs(g: &Vec<Vec<usize>>, p: usize, dp: &mut Vec<Vec<(usize, u64)>>, seen: &mut Vec<bool>) -> 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::<u64>()+1
}
fn dfs2(p: usize, dp: &mut Vec<Vec<(usize, u64)>>, seen: &mut Vec<bool>) -> 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::<u64>()+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::<u64>();
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);
}
分からず。 ABC394E - Palindromic Shortest Path にまとめたので、よければぜひ。 提出
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("\n"));
}