ABC394:Rustで解く！問題解説
AtCoder Beginner Contest 394のA~E問題をRustで解いた際の解法をまとめました。
A問題
問題
解説
文字列2 の文字だけを出力します。
コード
use proconio::{input, marker::Chars};
fn main() {
input!{
s: Chars,
}
// 2の文字だけを出力
for &ss in &s {
if ss == '2' { print!("{}", ss); }
}
println!();
}
B問題
問題
解説
(文字列の長さ, 入力順インデックス)のペアを作成し、文字列の長さの昇順にソートします。その後、ソート後の入力順インデックスに従って、元の文字列を出力します。
コード
use proconio::{input, marker::Chars};
fn main() {
input! {
n: usize,
s: [Chars; n],
}
// (文字列の長さ, index)のペアを昇順にする。
let mut len_list = Vec::new();
for i in 0..n {
len_list.push((s[i].len(), i));
}
len_list.sort();
// 昇順後のindex順に文字列を連結して出力
for i in 0..n {
// ソート後のインデックスを取得
let idx = len_list[i].1;
for &ss in &s[idx] {
print!("{}", ss);
}
}
println!();
}
C問題
問題
解説
問題文では以下のように書かれていますが、後ろから順番に WA を AC に置換することで解くことができます。
文字列中に登場する
WAのうち最も先頭のものをACに置換します。
理由は、文字 WA を AC に置き換えた後に、文字 C が表れたとしても、その位置以降で更なる置換が発生しないためです。言い換えれば、置き換え操作を行った位置以降の文字は、置換時期に影響を受けず、後ろから数量的に置き換えを進めることで漏れなく処理が行えることが分かります。
一方で、置き換えを行った位置より前の文字については、直前の文字が W であった場合、過去に遡って置換が必要になります。もし前から順番に置き換えをすると、過去の文字に戻って再度置き換えの必要性を確認しなければならなくなることがあり、効率的ではありません。
コード
use proconio::{input, marker::Chars};
fn main() {
input! {
mut s: Chars,
}
// 後ろからチェックして、WA→ACに書き換える
let sz = s.len();
for i in (0..sz - 1).rev() {
if s[i] == 'W' && s[i + 1] == 'A' {
s[i] = 'A';
s[i + 1] = 'C';
}
}
// 文字列を出力
for ss in s {
print!("{}", ss);
}
println!();
}
D問題
問題
解説
スタックの考え方を用いて問題を解くことができます。
文字列中の ( ) , [ ], < > の消去について考えます。まず、連続する2文字が以下の括弧のペアになっていれば消去します。
-
() -
[] -
<>
次に、消去した部分の前後にある文字でも同様にペアになっていれば、さらなる消去が可能です。これは、「消去した後の直前の文字」と「その次に現れた文字」をペアにして消せると言い換えられ、スタックのデータ構造を使うことで実現できます。
よって、文字を1つずつスタックに追加し、直前の2文字でペアにできれば順次消去を行うという処理を繰り返します。
コード
use proconio::{input, marker::Chars};
use std::collections::VecDeque;
fn main() {
input! {
s: Chars,
}
let sz = s.len();
// dequeに入れ、直前の2つが消せるなら消去する
let mut dq = VecDeque::new();
for i in 0..sz {
dq.push_back(s[i]);
if dq.len() >= 2 {
// 2つ取り出す
let back1 = dq.pop_back().unwrap();
let back2 = dq.pop_back().unwrap();
// 正しいペアでないなら、戻す
if !pair_check(back2, back1) {
dq.push_back(back2);
dq.push_back(back1);
}
}
}
// dqが空なら「Yes」、そうでなければ「No」
println!("{}", if dq.len() == 0 { "Yes" } else { "No" });
}
// 2つの文字がペアであるかをチェックする関数
fn pair_check(s1: char, s2: char) -> bool {
(s1 == '(' && s2 == ')') ||
(s1 == '[' && s2 == ']') ||
(s1 == '<' && s2 == '>')
}
E問題
問題
解説
回文が作れる条件を考えます。
- 0文字の場合: 開始点と終点が同じ頂点の場合のみ、可能
- 1文字の場合: 開始の頂点から遷移可能な頂点の場合に可能。
- 2文字以上の場合:
- 2文字の場合は、0文字の回文(1の状態)で両端に同じ文字を追加することで可能。
- 3文字の場合は、1文字の回文(2の状態)で両端に同じ文字を追加することで可能。
- 4文字の場合は、2文字の回文で両端に同じ文字を追加することで可能。
...
回文の状態から両端に同じ文字を追加することで新しい回文を作ることが可能。
したがって、(開始点, 終点)をペアとする状態キューを用意し、回文の最小文字数が小さい順にキューから取り出し、新たに作れる回文をキューに追加していけばよいです。
計算量は、状態数が
コード
use proconio::{input, marker::Chars};
use std::collections::VecDeque;
const INF: usize = 1 << 60;
fn main() {
input! {
n: usize,
c: [Chars; n],
}
// dp[開始地点s][終了地点t] = 回文の長さの最小値
let mut dp = vec![vec![INF; n]; n];
// 状態(開始点, 終点)のキュー
let mut dq = VecDeque::new();
// 回文の長さが0, 1の部分を初期化し、キューに追加
init0(n, &c, &mut dp, &mut dq);
init1(n, &c, &mut dp, &mut dq);
// キューを順番に取り出し
// 取り出した状態から両端に同じ文字を追加できる場合は、状態更新とキューを追加する
while let Some((m1, m2)) = dq.pop_front() {
for s in 0..n {
for t in 0..n {
// -以外で両端が同じ文字かをチェック
let left_char = c[s][m1];
let right_char = c[m2][t];
if !is_same_char(left_char, right_char) { continue; }
// DPの状態が更新可能なら、キューに追加
let next_len = dp[m1][m2] + 2;
if update_state(next_len, &mut dp, s, t) {
dq.push_back((s, t));
}
}
}
}
// dpのi行目を順番に出力
for i in 0..n {
for j in 0..n {
if dp[i][j] == INF { print!("-1 "); }
else { print!("{} ", dp[i][j]) }
}
println!();
}
}
fn init0(n: usize, _c: &Vec<Vec<char>>, dp: &mut Vec<Vec<usize>>, dq: &mut VecDeque<(usize, usize)>) {
for i in 0..n {
dp[i][i] = 0;
dq.push_back((i, i));
}
}
fn init1(n: usize, c: &Vec<Vec<char>>, dp: &mut Vec<Vec<usize>>, dq: &mut VecDeque<(usize, usize)>) {
for i in 0..n {
for j in 0..n {
if c[i][j] != '-' && dp[i][j] != 0 {
dp[i][j] = 1;
dq.push_back((i, j));
}
}
}
}
fn is_same_char(c1: char, c2: char) -> bool {
(c1 != '-') && (c2 != '-') && c1 == c2
}
fn update_state(next_len: usize, dp: &mut Vec<Vec<usize>>, s: usize, t: usize) -> bool {
// 更新しない場合
if next_len >= dp[s][t] { return false; }
// 更新する場合
dp[s][t] = next_len;
true
}
Discussion