ABC398:Rustで解く！問題解説
AtCoder Beginner Contest 398のA~E問題をRustで解いた際の解法をまとめました。
A問題
問題
解説
長さ = に置き換えたものを出力します。
-
が奇数の場合
中央の文字を=に置き換えます。このとき、中央のインデックスはです。 -
が偶数の場合
中央の2つの文字を=に置き換えます。このとき、中央のインデックスはと です。
コード
use itertools::Itertools;
use proconio::input;
fn main() {
// 入力
input! {
n: usize,
}
// 長さnの文字列を'-'で初期化
let mut ans = vec!['-'; n];
// nが奇数の場合
if n % 2 == 1 {
let mid = n / 2;
ans[mid] = '=';
}
// nが偶数の場合
else {
let mid1 = n / 2;
let mid2 = mid1 - 1;
ans[mid1] = '=';
ans[mid2] = '=';
}
// 結果を出力
println!("{}", ans.iter().join(""));
}
B問題
問題
解説
7枚のカードから5枚を選び、その5枚がフルハウス（同じ値のカードが3枚1組、別の同じ値のカードが2枚1組）になっているかを判定します。カードの選び方は、
フルハウスの判定方法としては、選んだ5枚のカードの値をカウントし、最も多い値の出現回数が3で、次に多い値の出現回数が2であればフルハウスと判定できます。
コード
use proconio::input;
fn main() {
let sz = 7;
// 入力
input! {
a: [usize; sz],
}
// 7枚のカードから5枚のカードの選び方を全て試す
let mut ans = false;
for i1 in 0..sz {
for i2 in i1+1..sz {
for i3 in i2+1..sz {
for i4 in i3+1..sz {
for i5 in i4+1..sz {
if is_fullhouse(a[i1], a[i2], a[i3], a[i4], a[i5]) {
ans = true;
}
}
}
}
}
}
// 出力
println!("{}", if ans { "Yes" } else { "No" });
}
// フルハウス判定関数
fn is_fullhouse(a: usize, b: usize, c: usize, d: usize, e: usize) -> bool {
// 1~13の各カードの出現枚数をカウント
let mut counts = vec![0; 14];
counts[a] += 1;
counts[b] += 1;
counts[c] += 1;
counts[d] += 1;
counts[e] += 1;
// 降順で最も多いカードの出現枚数が3,2であればフルハウス
counts.sort();
counts.reverse();
counts[0] == 3 && counts[1] == 2
}
C問題
問題
解説
-
値の出現回数を管理
連想配列（HashMap）を使用して、各値が何回出現するかを記録します。 -
条件を満たす人を探索
値が1回だけ出現する人を探し、その中で最も大きい値を持つ人を特定します。この際、値とその人の番号をペアとして管理し、最大値が更新されるたびにペアを更新します。 -
結果の出力
条件を満たす人がいない場合は-1を出力し、条件を満たす人がいる場合はその人の番号（1-indexed）を出力します。
コード
use proconio::input;
use std::collections::HashMap;
const INF : usize = 1 << 60;
fn main() {
// 入力
input! {
n: usize,
a: [usize; n],
}
// 連想配列で値の出現回数を管理
let mut freq = HashMap::new();
for &num in &a {
*freq.entry(num).or_insert(0) += 1;
}
// 値が1回だけ出現する中で最も大きい値とその人の番号を管理
let mut max_val = (0, INF);
for i in 0..n {
if let Some(&count) = freq.get(&a[i]) {
if count > 1 {
continue;
}
// 最大値を更新
if a[i] > max_val.0 {
max_val.0 = a[i];
max_val.1 = i;
}
}
}
// 出力
if max_val.1 == INF {
// 条件を満たす人がいない場合
println!("-1");
} else {
// 条件を満たす人の番号を出力（1-indexed）
println!("{}", max_val.1 + 1);
}
}
D問題
問題
解説
煙をシミュレーションしながら解きます。しかし、問題文の通りに煙を(0, 0)から発生させて、発生した煙を全て上下左右に動かす実装を行うと、時刻
そこで、煙を動かす操作を別の表現に置き換えます。具体的には、発生源と人を本来の動きと逆向きに動かすことで、各煙に対する発生源や人との相対距離が一致することを利用します。この方法では、1回の時刻に対して動かす対象が
この工夫により、実行制限時間内に問題を解くことが可能になります。
コード
use proconio::{input, marker::Chars};
use std::collections::HashSet;
use itertools::Itertools;
fn main() {
// 入力
input! {
n: usize,
r: i64, c: i64,
s: Chars,
}
// 煙の発生源の座標
let mut src = (0, 0);
// 人の座標
let mut person = (r, c);
// 発生した煙の座標集合
let mut smoke_set = HashSet::new();
let mut result = Vec::new();
// 動きをシミュレーション
for i in 0..n {
// 煙の発生
smoke_set.insert(src);
// 発生源と人を移動
move_pos(s[i], &mut src);
move_pos(s[i], &mut person);
// 人の座標が発生した煙の集合に含まれるかを判定
result.push(if smoke_set.contains(&person) { '1' } else { '0' });
}
// 出力
println!("{}", result.iter().join(""));
}
// 座標を移動させる関数
fn move_pos(direction: char, pos: &mut (i64, i64)) {
match direction {
'N' => pos.0 += 1,
'S' => pos.0 -= 1,
'W' => pos.1 += 1,
'E' => pos.1 -= 1,
_ => (),
}
}
E問題
問題
解説
この問題は、与えられた木に対して、奇閉路（閉路のサイズが奇数）を作らないように辺を追加するゲームです。プレイヤーは交互に辺を追加し、追加できなくなったプレイヤーが負けとなります。
奇閉路を作る条件は、ある2頂点間の移動距離が偶数のときに辺を追加する場合です。一方、移動距離が奇数の2頂点間に辺を追加した場合、必ず偶閉路が作られます。また、偶閉路を作った後も、移動距離の偶奇は変化しないため、移動距離が奇数の2頂点を選び続けるのが最適な戦略となります。
このゲームで自分が必ず勝つための戦略は以下の通りです。
-
先手・後手の選択
入力の木における全頂点間の移動距離が3以上の奇数のペア数が奇数ならFirst、偶数ならSecondを選択します。 -
自分の番での辺の選び方
入力で与えられていない2頂点のうち、まだ選択されていない移動距離が奇数のペアを選択して辺を追加します。
コード
use proconio::input_interactive;
use std::process::exit;
use std::cmp::min;
use std::collections::BTreeSet;
const INF: usize = 1 << 60;
fn main() {
// 入力
input_interactive! {
n: usize,
uv: [(i64, i64); n - 1], // 1始まりで考える
}
// 無向グラフの隣接行列の頂点間距離
let mut dist = vec![vec![INF; n + 1]; n + 1];
// 自身と入力で与えられている頂点間距離を初期化
dist_init(&mut dist, &uv, n);
// 全頂点間の距離を求める
calc_min_dist(&mut dist, n);
// 距離が3以上の奇数となるペアを全て取得
let mut st = get_odd_dist(&dist, n);
// ペアの個数が奇数ならFirst、偶数ならSecond
if st.len() % 2 == 1 {
println!("First");
} else {
println!("Second");
// 相手の番
cpu_turn(&mut st);
}
// 自分の番 → 相手の番でループ
loop {
my_turn(&mut st);
cpu_turn(&mut st);
}
}
fn dist_init(dist: &mut Vec<Vec<usize>>, uv: &Vec<(i64, i64)>, n: usize) {
// 自身への移動距離は0
for i in 1..=n {
dist[i][i] = 0;
}
// 入力で与えられている頂点間の移動距離は1
for &(u, v) in uv {
dist[u as usize][v as usize] = 1;
dist[v as usize][u as usize] = 1;
}
}
fn calc_min_dist(dist: &mut Vec<Vec<usize>>, n: usize) {
// 全頂点間の移動距離をワーシャルフロイド法で求める
for m in 1..=n {
for f in 1..=n {
for t in 1..=n {
dist[f][t] = min(dist[f][t], dist[f][m] + dist[m][t]);
}
}
}
}
fn get_odd_dist(dist: &Vec<Vec<usize>>, n: usize) -> BTreeSet<(usize, usize)> {
let mut st = BTreeSet::new();
// f < t のみ数える
for f in 1..=n {
for t in f + 1..=n {
if dist[f][t] >= 3 && dist[f][t] % 2 == 1 {
st.insert((f, t));
}
}
}
st
}
fn my_turn(st: &mut BTreeSet<(usize, usize)>) {
if !st.is_empty() {
let (u, v) = *st.iter().next().unwrap();
println!("{} {}", u, v);
st.remove(&(u, v));
}
}
fn cpu_turn(st: &mut BTreeSet<(usize, usize)>) {
input_interactive! {
u: i64, v: i64,
}
if u == -1 && v == -1 {
// 終了条件
exit(0);
} else {
if st.contains(&(u as usize, v as usize)) {
st.remove(&(u as usize, v as usize));
}
}
}
Discussion