ABC403:Rustで解く！問題解説
AtCoder Beginner Contest 403のA~E問題をRustで解いた際の解法をまとめました。
A問題
問題
解説
数列
コード
use proconio::input;
fn main() {
// 入力
input! {
n: usize,
a: [usize; n],
}
// 奇数番目（1-indexed）に対応する偶数インデックス（0-indexed）の値を足す
let mut ans = 0;
let mut cur_pos = 0;
while cur_pos < n {
ans += a[cur_pos];
cur_pos += 2;
}
// 出力
println!("{}", ans);
}
B問題
問題
解説
この問題は、文字列
文字列 ? はワイルドカードとして扱い、文字列
探索範囲は
コード
use proconio::{input, marker::Chars};
fn main() {
// 入力
input! {
t: Chars,
u: Chars,
}
// 部分文字列の一致判定
let mut found = false;
for start_pos in 0..=t.len() - u.len() {
if is_match(start_pos, &t, &u) {
found = true;
break;
}
}
// 結果を出力
println!("{}", if found { "Yes" } else { "No" });
}
// 部分文字列が一致するかを判定する関数
fn is_match(start_pos: usize, t: &Vec<char>, u: &Vec<char>) -> bool {
for i in 0..u.len() {
if t[start_pos + i] != '?' && t[start_pos + i] != u[i] {
return false;
}
}
true
}
C問題
問題
解説
この問題は、ユーザ
権限の管理は以下のように行います。
- 個別の閲覧権限：ユーザごとにHashSetを用いて管理します。
- 全体の閲覧権限：ユーザごとにbool型の配列を用いて管理します。
クエリに応じて以下の処理を行います。
- クエリ1（ユーザ
X Y - ユーザ
X HashSetにページY
- ユーザ
- クエリ2（ユーザ
X - ユーザ
X trueに設定します。
- ユーザ
- クエリ3（ユーザ
X Y - 以下の条件で判定します。
- 全体権限が
trueの場合：閲覧可能 - 全体権限が
falseかつHashSetにページY - 上記いずれにも該当しない場合：閲覧不可
- 全体権限が
- 以下の条件で判定します。
コード
use proconio::{input, marker::Usize1};
use std::collections::HashSet;
fn main() {
// 入力
input! {
n: usize, _m: usize, q: usize,
}
// 各ユーザの個別の閲覧権限を管理するHashSet
let mut perm_pages = vec![HashSet::new(); n];
// 各ユーザの全体権限を管理するフラグ
let mut all_allow = vec![false; n];
// クエリ処理
for _ in 0..q {
input! {
query_type: usize,
}
if query_type == 1 {
// クエリ1: ユーザXにページYの権限を付与
input! {
x: Usize1, y: Usize1,
}
perm_pages[x].insert(y);
} else if query_type == 2 {
// クエリ2: ユーザXに全体権限を付与
input! {
x: Usize1,
}
all_allow[x] = true;
} else if query_type == 3 {
// クエリ3: ユーザXがページYの権限を持っているか判定
input! {
x: Usize1, y: Usize1,
}
if all_allow[x] || perm_pages[x].contains(&y) {
println!("Yes");
} else {
println!("No");
}
}
}
}
D問題
問題
解説
この問題は、整数列
以下の1~4の手順を考えることで解くことができます。
-
整数列
A
元の整数列A A A D A_j - A_i = D -
余りによるグループ分け
D D D D=0 -
グループごとの削除個数の最小化
各グループ内で、差がD - 状態:
dp[\text{cur}][\text{選択}] -
\text{cur} -
\text{選択} 0 1
-
- 遷移:
- 削除する場合: 前回の状態が削除/非削除のどちらでも遷移可能
- 削除しない場合: 前回の状態が削除である必要がある。ただし、前回の値との差が
D
- 状態:
-
D=0
D=0 A
具体的には、n - \text{種類数}
以上をまとめると、整数列
コード
use proconio::input;
use std::collections::{HashSet, BTreeMap};
use std::cmp::min;
const INF: usize = 1 << 60;
fn main() {
// 入力
input! {
n: usize, d: usize,
mut a: [usize; n],
}
a.sort();
// Dが0のときの解法
if d == 0 {
solve_d_zero(n, &a);
}
// Dが0でないときの解法
else {
solve_d_nonzero(d, &a);
}
}
fn solve_d_zero(n: usize, a: &Vec<usize>) {
// Aの重複を排除した分が答え
let mut unique_elements = HashSet::new();
for &value in a {
unique_elements.insert(value);
}
println!("{}", n - unique_elements.len());
}
fn solve_d_nonzero(d: usize, a: &Vec<usize>) {
// Aの各値を昇順にまとめる
let mut frequency_map = BTreeMap::new();
for &value in a {
*frequency_map.entry(value).or_insert(0) += 1;
}
// Dで割った余りでグループ分け
let mut groups = vec![Vec::new(); d];
for (&key, &_value) in &frequency_map {
let idx = key % d;
groups[idx].push(key);
}
let mut ans = 0;
// グループごとにDP
for group in groups {
let sz = group.len();
// DP[cur個目まで見た][cur個目の選択(削除/非削除)] = 削除個数の最小値
let mut dp = vec![vec![INF; 2]; sz + 1];
dp[0][0] = 0; // 初期状態: 削除
dp[0][1] = 0; // 初期状態: 非削除
// DP遷移
for cur in 1..=sz {
let del_cnt = *frequency_map.get(&group[cur - 1]).unwrap();
// 削除する場合
dp[cur][0] = min(dp[cur - 1][0], dp[cur - 1][1]) + del_cnt;
// 削除しない場合
dp[cur][1] = dp[cur - 1][0];
if cur == 1 || group[cur - 1] - group[cur - 2] != d {
dp[cur][1] = min(dp[cur][1], dp[cur - 1][1]);
}
}
// グループ内の最小削除個数を加算
ans += min(dp[sz][0], dp[sz][1]);
}
// 出力
println!("{}", ans);
}
E問題
問題
解説
この問題は、集合
各クエリで集合
そこで、Trie木というデータ構造を用いることで、接頭辞の判定を効率化します。Trie木は、文字列の先頭部分の共通部分を共有して保存する木構造で、各文字を順番に辿ることで接頭辞を効率よく管理できます。
以下の1~2の手順で問題を解きます。
-
Trie木の構築
全てのクエリ情報を先に読み込み、Trie木を構築します。この際、各文字列の末端ノードを記録します。 -
クエリ処理
- クエリが
T = 1 X - 追加した文字列が指すノードとその子ノード全てを切り離します。また、切り離したノードで数えていた接頭辞でない文字列の個数を減らします。
- クエリが
T = 2 Y - 追加する文字列が切り離されていないノードであれば、接頭辞でない文字列の個数をインクリメントします。
- クエリが
この方法により、効率よく接頭辞の判定を行い、計算量を削減できます。
コード
use proconio::input;
use std::collections::HashMap;
fn main() {
// 入力
input! {
q: usize,
}
// クエリ情報を格納
let mut t = vec![0; q];
let mut s = vec![String::new(); q];
input_ts(&mut t, &mut s, q);
// Trie木の構築
let mut trie = Trie::new();
let mut nodelist = Vec::new();
for i in 0..q {
let node = trie.add_string(&s[i]);
nodelist.push(node);
}
// Trie木のカウントを初期化
trie.initialize_count();
// クエリ処理
for i in 0..q {
if t[i] == 1 {
trie.regist_x(nodelist[i]);
} else {
trie.regist_y(nodelist[i]);
}
println!("{}", trie.ans);
}
}
// クエリ情報を入力
fn input_ts(t: &mut Vec<usize>, s: &mut Vec<String>, q: usize) {
for i in 0..q {
input! {
tt: usize,
ss: String,
}
t[i] = tt;
s[i] = ss;
}
}
// Trie木の構造体
struct Trie {
node: Vec<HashMap<char, usize>>, // ノード：[文字] = 次のノードのインデックス
ans: usize, // 接頭辞でない文字列の個数
connect: Vec<bool>, // ノードの連結状態
cnt_y: Vec<usize>, // 集合Yに追加されたノードの文字列数
}
impl Trie {
fn new() -> Self {
Trie {
node: vec![HashMap::new()],
ans: 0,
connect: Vec::new(),
cnt_y: Vec::new(),
}
}
// 文字列をTrie木に追加し、末端ノードのインデックスを返す
fn add_string(&mut self, s: &str) -> usize {
let mut cur = 0;
for c in s.chars() {
if let Some(&next) = self.node[cur].get(&c) {
cur = next;
} else {
let new_idx = self.node.len();
self.node.push(HashMap::new());
self.node[cur].insert(c, new_idx);
cur = new_idx;
}
}
cur
}
// Trie木のカウントを初期化
fn initialize_count(&mut self) {
self.ans = 0;
let n = self.node.len();
self.connect = vec![true; n];
self.cnt_y = vec![0; n];
}
// 集合Xに文字列を追加
fn regist_x(&mut self, cur: usize) {
if !self.connect[cur] {
return;
}
self.connect[cur] = false;
self.ans -= self.cnt_y[cur];
let children: Vec<usize> = self.node[cur].values().cloned().collect();
for next in children {
self.regist_x(next);
}
}
// 集合Yに文字列を追加
fn regist_y(&mut self, cur: usize) {
if !self.connect[cur] {
return;
}
self.cnt_y[cur] += 1;
self.ans += 1;
}
}
Discussion