👨🍳
緑コーダーがRustで解説してみた(ABC424 A～E)
AtCoder Beginner Contest 424のA～E問題を緑コーダーが自分なりの解説と解答コードをまとめました。
参考になりましたら幸いです。
ABC424-A
問題
与えられた三角形が二等辺三角形かどうかを判定する問題です。
解説
二等辺三角形の条件は、「三角形の3辺のうち2辺の長さが等しい」ことなので、それを判定します。
なお、この問題では、正三角形（3辺がすべて等しい場合）も二等辺三角形として扱ってよいとされています。
そのため、3辺のうち少なくとも2辺が等しいかどうかを判定すればよいです。
コード
abc424a.rs
use proconio::input;
fn main() {
// 入力
input! {
a: usize, b: usize, c: usize, // 三角形の各辺の長さ
}
// 二等辺三角形かどうかを判定して出力
println!("{}", if is_isosceles(a, b, c) { "Yes" } else { "No" });
}
// 二等辺三角形かどうかを判定する関数
fn is_isosceles(a: usize, b: usize, c: usize) -> bool {
a == b || b == c || c == a
}
ABC424-B
問題
解説
この問題では、各人が正解した課題を管理し全ての課題に正解した場合にその人を記録していきます。
各人が正解した課題を、 HashSet で管理し、入力として与えられるイベント（誰がどの課題を正解したか）を順番に処理します。
各人の正解した課題数が
最後に、全問正解者を順番に出力します。
コード
abc424b.rs
use proconio::input;
use std::collections::HashSet;
use itertools::Itertools;
fn main() {
// 入力
input! {
n: usize, // 人数
m: usize, // 各人が解くべき課題数
k: usize, // イベント数
}
// 各人の正解した課題を管理する集合
let mut ans_st = vec![HashSet::new(); n + 1];
// 全問正解した人のリスト
let mut ans = Vec::new();
// 各イベントを処理
for _ in 0..k {
input! {
a: usize, // 正解した人 (1-index)
b: usize, // 課題番号
}
// 課題番号を集合に追加
ans_st[a].insert(b);
// M問全問正解したら記録
if ans_st[a].len() == m {
ans.push(a);
}
}
// 全問正解した人を出力
println!("{}", ans.iter().join(" "));
}
ABC424-C
問題
解説
各スキルを頂点、スキル習得の前後関係を有向辺とするグラフを構築します。
具体的には、スキル
- スキル
A i - スキル
B i
次に、事前に習得が必要でないスキル（スキル 0）を始点として深さ優先探索（DFS）を行います。
この探索により、到達可能な頂点（スキル）の数を数えることで、習得可能なスキルの個数を求められます。
コード
abc424c.rs
use proconio::input;
fn main() {
// 入力
input! {
n: usize, // スキルの個数
}
// スキル習得のグラフを作る
let graph = make_graph(n);
// 探索済みのスキルを記録する配列
let mut seen = vec![false; n + 1];
// 深さ優先探索を実行
dfs(0, &graph, &mut seen);
// 1~Nの中で習得できたスキルの個数を数える
let mut cnt = 0;
for i in 1..=n {
if seen[i] {
cnt += 1;
}
}
// 習得可能なスキルの個数を出力
println!("{}", cnt);
}
// グラフを構築する関数
fn make_graph(n: usize) -> Vec<Vec<usize>> {
let mut graph = vec![Vec::new(); n + 1];
// 各スキルで取得可能なものを入力で受け取る
for i in 1..=n {
input! {
a: usize, b: usize, // 取得に必要なスキル(aまたはb)
}
graph[a].push(i);
graph[b].push(i);
}
graph
}
// 深さ優先探索を行う関数
fn dfs(cur: usize, graph: &Vec<Vec<usize>>, seen: &mut Vec<bool>) {
// 現在のスキルを訪問済みにする
seen[cur] = true;
// 現在のスキルから次に習得できるスキルを探索
for &next in &graph[cur] {
if seen[next] {
continue;
}
dfs(next, graph, seen);
}
}
ABC424-D
問題
解説
2×2の黒マスを作らないためには、各2×2の領域に少なくとも1つの白マスが必要です。
したがって、白マスへの置き換えの必要回数はおおよその下限値として
これを踏まえたうえで、マス目を左上から順に見ていき、以下1~4のルールに従って再帰的に探索を進めます。
- 探索打ち切り
現在の操作回数が暫定の最小操作回数を超えた場合、探索を打ち切ります。 - 全てのマスを見終わった場合
操作回数の最小値を更新します。 - 現在のマスとその右、下、右下のいずれかに白マスがある場合
そのまま次のマスを見ます。 - 現在のマスとその右、下、右下が全て黒マスの場合
いずれかのマスを白マスに置き換え、次のマスを見ます。
コード
abc424d.rs
use proconio::{input, marker::Chars};
use std::cmp::min;
fn main() {
// テストケース数の入力
input! {
t: usize,
}
for _ in 0..t {
solve();
}
}
fn solve() {
// 入力
input! {
h: usize, w: usize, // マス目の縦横
mut s: [Chars; h], // マス目の情報
}
// 操作回数(暫定の最大値で初期化)
let mut ans = h * w / 4;
// 置き換えを再帰的に試した結果の最小回数を出力
rec(h, w, &mut s, 0, 0, 0, &mut ans);
println!("{}", ans);
}
fn rec(
h: usize, w: usize, // マス目の縦横
s: &mut Vec<Vec<char>>, // マス目の情報
ci: usize, cj: usize, // 現在の座標
cnt: usize, // 操作回数
ans: &mut usize, // 操作回数の最小値
) {
// 暫定の操作回数に到達したら打ち切る
if cnt >= *ans { return; }
// 全てのマスまで到達したら、操作回数の最小値を更新
if ci == h && cj == 0 {
*ans = min(*ans, cnt);
return;
}
// 次のマスの座標
let (ni, nj) = get_pos(h, w, ci, cj, 0, 1);
// 今、右、下、右下のいずれかが白マスなら、そのまま次を見る
if has_white(h, w, s, ci, cj) {
rec(h, w, s, ni, nj, cnt, ans);
}
// 今、右、下、右下が全て黒マスなら、いずれかのマスを置き換えて次を見る
else {
for i in 0..2 {
for j in 0..2 {
// 置き換えるマスの座標
let (put_i, put_j) = get_pos(h, w, ci, cj, i, j);
// 置き換え実施
s[put_i][put_j] = '.';
// 次を見る
rec(h, w, s, ni, nj, cnt + 1, ans);
// 置き換えを戻す
s[put_i][put_j] = '#';
}
}
}
}
fn has_white(
h: usize, w: usize, // マス目の縦横
s: &mut Vec<Vec<char>>, // マス目の情報
ci: usize, cj: usize // 現在の座標
) -> bool {
// 今、右、下、右下を調べる
for i in 0..2 {
for j in 0..2 {
let ni = ci + i;
let nj = cj + j;
// 範囲外のマスは白マスとする
if ni >= h || nj >= w { return true; }
// 白のマスあり
if s[ni][nj] == '.' { return true; }
}
}
false
}
fn get_pos(
_h: usize, w: usize, // マス目の縦横
ci: usize, cj: usize, // 現在の座標
add_i: usize, add_j: usize // 座標の加算値
) -> (usize, usize) {
let mut ni = ci + add_i;
let mut nj = cj + add_j;
// 横座標が範囲外なら、次の行の左端に進める
if nj >= w {
ni += 1;
nj -= w;
}
(ni, nj)
}
ABC424-E
問題
解説
棒の長さを管理するために、優先度付きキュー BinaryHeap を使用します。
これにより、常に最も長い棒を効率的に取り出せます。
操作回数
また、優先度付きキューに棒の長さの情報を追加する際、浮動小数点数の扱いを避けるため、整数として管理します。
1本の棒に対してまとめて半分に切るという操作は、最大で
コード
abc424e.rs
use std::collections::BinaryHeap;
use proconio::input;
// 長さをスケーリングするための定数
const EXTRA: u64 = 1 << 30;
// 棒の長さと本数を管理する構造体
#[derive(PartialEq, Eq, PartialOrd, Ord, Clone)]
struct Rod {
length: u64,
cnt: u64,
}
fn main() {
// テストケース数の入力
input! {
t: usize,
}
for _ in 0..t {
solve();
}
}
fn solve() {
input! {
n: usize, // 初めの棒の数
k: u64, // 操作回数
x: u64, // 答える棒の順番
mut a: [u64; n], // 初めの各棒の長さ
}
// 各棒の長さをスケーリング
for i in 0..n {
a[i] *= EXTRA;
}
// 棒を優先度付きキューにセットする
let mut hp = set_hp(a);
// 合計K回のカットを実施
exec_cut(k, &mut hp);
// X番目を取り出す
let val = exec_pop(x, &mut hp);
// スケーリングした長さを元に戻して出力
println!("{}", val as f64 / EXTRA as f64);
}
// 優先度付きキューに初期の棒をセット
fn set_hp(a: Vec<u64>) -> BinaryHeap<Rod> {
let mut hp = BinaryHeap::new();
for aa in a {
hp.push(Rod { length: aa, cnt: 1 });
}
hp
}
// 棒を切断する操作
fn exec_cut(mut rest: u64, hp: &mut BinaryHeap<Rod>) {
while let Some(rod) = hp.pop() {
// 残り回数以上の場合は一部カット、残りは戻す
if rod.cnt >= rest {
// カットする分の追加
let cuts = rest;
set_cut_rod(rod.length, cuts, hp);
// カットしない分の追加
let back = rod.cnt - rest;
back_rod(rod.length, back, hp);
break;
} else {
// 全てカットして追加
set_cut_rod(rod.length, rod.cnt, hp);
// カット回数の更新
rest -= rod.cnt;
}
}
}
// X番目に大きい棒を取り出す
fn exec_pop(mut rest: u64, hp: &mut BinaryHeap<Rod>) -> u64 {
while let Some(rod) = hp.pop() {
// 残り回数以上の場合は、その時の長さを取得
if rod.cnt >= rest {
return rod.length;
} else {
// カット回数の更新
rest -= rod.cnt;
}
}
0
}
// 切断後の棒を追加
fn set_cut_rod(length: u64, cnt: u64, hp: &mut BinaryHeap<Rod>) {
hp.push(Rod { length: length / 2, cnt: cnt * 2 });
}
// 切断しなかった棒を戻す
fn back_rod(length: u64, cnt: u64, hp: &mut BinaryHeap<Rod>) {
hp.push(Rod { length, cnt });
}
Discussion