👨🍳
ABC384:Rustで解く！問題解説
AtCoder Beginner Contest 384のA~E問題をRustで解いた際の解法をまとめました。
A問題
- 問題
- 解説
文字列
- コード
use proconio::{input, marker::Chars};
use itertools::Itertools;
fn main() {
input! {
n: usize, c1: char, c2: char,
mut s: Chars,
}
for i in 0..n {
if s[i] != c1 {
s[i] = c2;
}
}
println!("{}", s.iter().join(""));
}
B問題
- 問題
- 解説
実際にシミュレーションして解きます。各ラウンドで以下のいずれかの条件を満たす場合に、レーティングに
-
D -
D
- コード
use proconio::input;
fn main() {
input! {
n: usize, r: i64,
}
let mut now = r; // 現在のレーティング
for _ in 0..n {
input! {
d: usize, a: i64,
}
if d == 1 {
if now >= 1600 && now <= 2799 {
now += a;
}
} else {
if now >= 1200 && now <= 2399 {
now += a;
}
}
}
println!("{}", now); // 最終的なレーティングを出力
}
C問題
- 問題
- 解説
合計値を降順にし、同点の場合は名前を昇順にするために、合計値の符号を反転させます。
これにより、合計値と名前を一緒に昇順にソートすることが可能になります。
- コード
use itertools::Itertools;
use proconio::input;
fn main() {
let n = 5;
let mut score = vec![0; n];
for i in 0..n {
input!{
x: i64,
}
score[i] = x;
}
// 文字リスト
let moji = vec!['A', 'B', 'C', 'D', 'E'];
let mut ans = Vec::new();
// bit全探索(集合のすべての部分集合を試す)
let sz = 1 << n;
for state in 1..sz {
let mut ret = 0;
let mut name = Vec::new();
for bits in 0..n {
if state & (1 << bits) != 0 {
ret -= score[bits];
name.push(moji[bits]); // 選んだbitの文字を連結
}
}
// 人を辞書順(昇順)でするため、
// (スコア値を-1倍, 人)で管理
ans.push((ret, name.clone()));
}
ans.sort();
// 人の名前を順番に出力
for (_val, name) in &ans {
println!("{}", name.iter().join(""));
}
}
D問題
- 問題
- 解説
合計
- 数列
A - 数列
A - 数列
A
2と3で連続して選んだときの累積値は事前に計算しておきます。
また、2と3の選び方については、両方を全探索すると計算量が
- コード
use proconio::input;
const INF: usize = 1 << 60;
fn main() {
input! {
n: usize, s: usize,
a: [usize; n],
}
// 左からの累積和を計算
let mut acc_l = vec![0; n + 1];
for i in 0..n {
acc_l[i + 1] = acc_l[i] + a[i];
}
// 右からの累積和を計算
let mut acc_r = vec![0; n + 1];
for i in 0..n {
acc_r[i + 1] = acc_r[i] + a[n - 1 - i];
}
// aの数列に基づいて、sを超えない範囲で周期数 × Aの合計分を取る
// 端数をrest_sとする
let mut rest_s = s % acc_l[n];
for _ in 0..2 {
// aを右からi個選び、aを左からj個選んで端数と一致するか確認
for i in 0..=n {
if rest_s < acc_r[i] { break; }
let tmp_rest = rest_s - acc_r[i];
let j = below_bound(&acc_l, tmp_rest);
if j >= INF { continue; }
if acc_l[j] == tmp_rest {
// ちょうどsになる
println!("Yes");
return;
}
}
// 1周期前のものも試す
if rest_s + acc_l[n] <= s {
rest_s += acc_l[n];
}
}
// 見つからなかった場合
println!("No");
}
// 二分探索
// x以下の最大のposを返す。0番目より小さい値では異常値として、INFを返す
pub fn below_bound<T: std::cmp::PartialOrd>(vec: &Vec<T>, val: T) -> usize {
let mut l = 0;
let mut r = vec.len();
while r - l > 0 {
let m = (l + r) / 2;
if vec[m] <= val {
l = m + 1;
} else {
r = m;
}
}
if l == 0 { INF } else { l - 1 }
}
E問題
- 問題
- 解説
まず、初めのマスから上下左右を見て、吸収可能なマスを優先度付きキューに追加します。優先度付きキューを使うことで、マスの値が小さい順に取り出すことが出来るようになります。その後、以下の操作を可能な限り繰り返します。
キューの先頭にある値が現在の値の
さらに、取り出したマスから上下左右を見て、まだ追加していないマスがあれば、キューに追加します。
- コード
use proconio::{input, marker::Usize1};
use std::collections::BinaryHeap;
use std::cmp::Reverse;
fn main() {
const D4: [(usize, usize); 4] = [(!0, 0), (0, !0), (1, 0), (0, 1)]; // 上左下右
input! {
h: usize, w: usize, x: usize,
p: Usize1, q: Usize1,
s: [[usize; w]; h],
}
// 初めのマスを取得
let cpos = (p, q);
// キュー追加済みのマスを管理 (初めのマスは、キュー追加済み扱いとする。)
let mut used = vec![vec![false; w]; h];
used[cpos.0][cpos.1] = true;
// 現在の強さ
let mut ret = s[cpos.0][cpos.1];
// 吸収可能なマスのキュー
let mut hp = BinaryHeap::new();
// 上下左右を見て、次に吸収できるところを探す
for &dd in &D4 {
let nx = cpos.0.wrapping_add(dd.0);
let ny = cpos.1.wrapping_add(dd.1);
if nx >= h || ny >= w || used[nx][ny] { continue; }
// キューに追加
let nval = s[nx][ny];
hp.push(Reverse((nval, nx, ny))); // (強さ、座標x、座標y)
used[nx][ny] = true;
}
// キューがなくなるまで行う
while hp.len() > 0 {
// キューから先頭の要素を取り出す
let (cval, cx, cy) = hp.peek().unwrap().0;
// 1/x倍未満のものがない場合は終了
if (ret - 1) / x < cval { break; }
// キューから取り出して、強さを加算
hp.pop().unwrap();
ret += cval;
// 上下左右を見て、次に吸収できるところを探す
for &dd in &D4 {
let nx = cx.wrapping_add(dd.0);
let ny = cy.wrapping_add(dd.1);
if nx >= h || ny >= w || used[nx][ny] { continue; }
// キューに追加
let nval = s[nx][ny];
hp.push(Reverse((nval, nx, ny)));
used[nx][ny] = true;
}
}
// 最終結果を出力
println!("{}", ret);
}
Discussion