はじめに
AtCoder Beginner Contest 394のA-FをRustで解いてみました。
今回は残念ながら野暮用があったため、コンテストに参加できませんでしたが、解いた過程をQiitaに残します。
問題は各見出しのリンクからご覧ください。
私達ハウインターナショナルでは、社名をもじってハウッカソンという名のイベントを毎月最終金曜日に実施しています。
ハウッカソンのテーマに競技プログラミングを選ぶメンバーもいます。
A問題
文字列に含まれた2以外の文字を削除すればいいだけです。
カッコつけて正規表現で解きました。
use proconio::*;
use regex::Regex;
fn main() {
input! {
s: String
}
let reg = Regex::new("[^2]").unwrap();
let ans = reg.replace_all(&s, "");
println!("{}", ans);
}
B問題
ソートできるかな問題です。
文字列の長さをターゲットにしてソートしてあげましょう。
こういう配列系の操作はitertoolsというクレートなしでは書けない体になってしまいました。
use proconio::*;
use itertools::Itertools;
fn main() {
input! {
n: usize,
s: [String; n]
}
let mut s = s.iter().map(|e| (e.len(), e)).collect_vec();
s.sort_by_key(|e| e.0);
let ans = s.iter().map(|e| e.1).join("");
println!("{}", ans);
}
C問題
WAを置換してACにする問題です。
前から見ていって答えをvectorに入れていって、WAが見つかったらACに置換する方法だと、
WWAという入力の時に困ります。
(WWA => WACとなり、先頭に新しいWAが生まれてしまう)
そこで、答えのvectorにACを突っ込むのではなくて、回している入力sの先頭にAC文字列を入れてあげれば良さそうです。
| 答えベクタ | 入力ベクタ |
|---|---|
| [] | [W, W, A] |
| [W] | [W, A] |
| [W, W] | [A] |
| [W] | [A, C] |
| [] | [A, C, C] |
| ... | ... |
| [A, C, C] | [] |
今回はsのサイズがでかいのでsをベクタでとるとTLEします。
そこで先頭へのpushも定数倍で操作可能なdequeを使いましょう。
use std::collections::VecDeque;
use proconio::{marker::Chars, *};
use itertools::Itertools;
fn main() {
input! {
s: Chars
}
let mut s = VecDeque::from(s);
let mut ans = vec![];
while !s.is_empty() {
let first = s.pop_front().unwrap();
if first != 'A' {
ans.push(first);
continue;
}
if ans.is_empty() {
ans.push(first);
continue;
}
let &last = ans.last().unwrap();
if last != 'W' {
ans.push(first);
continue;
}
ans.pop();
s.push_front('C');
s.push_front('A');
}
println!("{}", ans.iter().join(""));
}
D問題
ほぼC問題と同じです。
), ], >が入ってきたらstackの一番上見て対応してるカッコかを確認すればよいだけです。
最後に(, [, <が連打されていたときに"No"が出力されることなくループが終了するので、
stackが空になっているかを確認して終了です。
use proconio::{marker::Chars, *};
fn main() {
input! {
s: Chars
}
let mut ans = vec![];
for &c in s.iter() {
if c == '(' || c == '[' || c == '<' {
ans.push(c);
continue;
}
if ans.is_empty() {
return println!("No");
}
let &last = ans.last().unwrap();
if c == '>' {
if last != '<' {
return println!("No");
}
ans.pop();
}
if c == ')' {
if last != '(' {
return println!("No");
}
ans.pop();
}
if c == ']' {
if last != '[' {
return println!("No");
}
ans.pop();
}
}
if ans.is_empty() {
println!("Yes");
} else {
println!("No");
}
}
E問題
難しかったですー。
先頭からやろうとすると苦しいです。
作るべきパスは回文になっていなきゃいけないので最後にそのパスが回文になっているかを判定しなければならないため、
これまで通ってきた文字列を持ってループしなくてはならないためです。
そこで、回文の中心から決めていくことを考えます。(ここは行間ありますが考察して辿り着きました)
ある回文があったとき(空文字も回文とみなします)その文字列の両端に何かしらの文字を加えてさらに長い回文を作るときの条件としては両端に同じ文字が来る場合です。
このようにして中心からきめていく回文の場合であれば内側の文字は回文であることを保証してループできるので前の情報を持っておく必要がなくなって嬉しいです。
よって、dp[i][j] := i->jの回文を作ることができる最短パスの長さ
としてdpを定義すると、
- ii->iへ文字cを追加して辿れる頂点
- j->jjへ文字cを追加して辿れる頂点
への遷移が可能になるので、dp[i][j]->dp[ii][jj]への遷移ができます。(この遷移で新しく2本のパスを追加するのでdp[i][j] + 2すれば遷移できることがわかりますね)
よってこれはダイクストラ法を使えば解けそうですね。
ダイクストラの出発地点はdp[i][i](=0)の頂点とc[i][j] != '-'のときのdp[i][j](=1)の頂点です。
計算量はO(n^4 * log(n))くらいでTLE踏みそうな気がしながら提出しましたが、
お祈りしていたら通りました。
use std::{cmp::Reverse, collections::{BinaryHeap, HashSet}};
use proconio::{marker::Chars, *};
use itertools::Itertools;
fn main() {
input! {
n: usize,
c: [Chars; n]
}
let mut pre = vec![vec![]; n];
let mut next = vec![vec![]; n];
for i in 0..n {
for j in 0..n {
if c[i][j] == '-' {
continue;
}
pre[j].push((i, c[i][j]));
next[i].push((j, c[i][j]));
}
}
let mut dp = vec![vec![usize::MAX; n]; n];
let mut heap = BinaryHeap::new();
for i in 0..n {
dp[i][i] = 0;
heap.push((Reverse(0), i, i));
}
for i in 0..n {
for j in 0..n {
if c[i][j] == '-' {
continue;
}
if dp[i][j] != usize::MAX {
continue;
}
dp[i][j] = 1;
heap.push((Reverse(1), i, j));
}
}
let mut det = HashSet::new();
while !heap.is_empty() {
let (_cost, i, j) = heap.pop().unwrap();
if det.contains(&(i, j)) {
continue;
}
det.insert((i, j));
for &(ii, iic) in pre[i].iter() {
for &(jj, jjc) in next[j].iter() {
if iic != jjc {
continue;
}
if det.contains(&(ii, jj)) {
continue;
}
let nc = dp[i][j] + 2;
if dp[ii][jj] > nc {
dp[ii][jj] = nc;
heap.push((Reverse(nc), ii, jj));
}
}
}
}
for i in 0..dp.len() {
let ans = dp[i].iter().map(|&e| if e == usize::MAX {-1} else {e as isize}).join(" ");
println!("{}", ans);
}
}
F問題
個人的にはE問題よりこっちの方が取り掛かりやすかった印象です。
木dpをします。
木dpの基本として適当な根を1つ決めてbottom upでdpの値を更新していくイメージでやってます。
適当な根を1つ決めることによって部分木を定義できるので以下のようにdpを定義します
dp[i] := 頂点iを根とする部分木に対するアルカングラフの頂点の最大値
さて部分木についてかんがえると、葉である場合とアルカンの中心部分(次数が4のやつ)を含むものの2つがあうことが考察できます。
これを考慮しつつ上の部分木へと更新していきます。
部分木iでアルカンとして選ぶことができる子アルカンは遷移の際には3つだけなので更新時には大きい方から3つ選んでいってあげます。
これで遷移はできましたが、答えの更新にはもう一つ考慮することがあります。
iが根とした場合のiの子は下記の2種類のパターンになると思います。
- iが葉の場合
- iに4つのアルカン部分木がくっついているパターン
葉の場合にはその頂点にくっつくアルカンの中心頂点 + 1をansと比較、
そうでない場合はアルカン部分木のサイズの大きいほうから4つを選んで比較
という方法をとればよいです。
コード末尾で、アルカンになり得ない接続がされた時の対処として a <= 3のアルカンはないことを明示しています。
(F問題、文字にして何をしているかを表現するのが非常に難しい)
use std::cmp::{max, Reverse};
use proconio::{marker::Usize1, *};
fn dfs(v: usize, g: &Vec<Vec<usize>>, target: &mut usize, pre: usize) -> usize {
let mut total = 1;
let mut sizes = vec![];
for &v2 in g[v].iter() {
if pre == v2 {
continue;
}
let ret = dfs(v2, g, target, v);
sizes.push(ret);
}
sizes.sort_by_key(|&e| Reverse(e));
if sizes.len() >= 3 {
let mut tk = 0;
for i in 0..3 {
tk += sizes[i];
}
total = max(total, tk + 1);
}
if sizes.len() >= 4 {
let mut tk = 0;
for i in 0..4 {
tk += sizes[i];
}
*target = max(*target, tk + 1);
}
if sizes.len() >= 1 {
let tk = sizes[0];
*target = max(*target, tk + 1);
}
total
}
fn main() {
input! {
n: usize,
ab: [(Usize1, Usize1); n - 1]
}
let mut g = vec![vec![]; n];
for &(a, b) in ab.iter() {
g[a].push(b);
g[b].push(a);
}
let mut target = 0;
dfs(0, &g, &mut target, usize::MAX);
if target <= 3 {
return println!("-1");
}
println!("{}", target);
}