👨🍳
緑コーダーがRustで解説してみた(ABC425 A～F)
AtCoder Beginner Contest 425のA～F問題を緑コーダーが自分なりの解説と解答コードをまとめました。
参考になりましたら幸いです。
ABC425-A
問題
以下の数式を計算する問題です。
解説
1から
累乗計算には pow 関数を使用すると便利です。
コード
abc425a.rs
use num::pow;
use proconio::input;
fn main() {
// 入力
input! {
n: i64, // 数列の項数
}
// N項の総和を計算
let mut ans = 0;
for i in 1..=n {
ans += pow(-1, i as usize) * pow(i, 3);
}
// 答えを出力
println!("{}", ans);
}
ABC425-B
問題
数列
解説
1から
数列
そのため、まず数列
もし同じ数字が2回以上現れていれば、1から No を出力します。
次に、数列
リストアップした中で、 -1 をそのリストから順番に置き換えることで、1から
コード
abc425b.rs
use std::collections::HashSet;
use proconio::input;
fn main() {
// 入力
input! {
n: usize, // 数列の長さ
a: [i64; n], // 数列の値
}
// -1以外の数字について、同じ数が2つ以上ないかをチェック
if is_multiple_value(n, &a) {
// 条件を満たさない
println!("No");
return;
}
// 条件を満たす
println!("Yes");
// aに含まれない数字を探す
let mut non_used = get_no_used_value(n, &a);
// 並び替え後の数列を出力
for idx in 0..n {
// -1なら使用していない数を取り出して置き換え
let mut val = a[idx];
if val == -1 {
val = *non_used.iter().next().unwrap();
non_used.remove(&val);
}
print!("{} ", val);
}
println!();
}
// 数列に同じ値が複数存在するかを判定
fn is_multiple_value(n: usize, a: &Vec<i64>) -> bool {
let mut used = vec![false; n+1];
for &aa in a {
if aa == -1 { continue; }
if used[aa as usize] {
return true;
}
used[aa as usize] = true;
}
false
}
// 数列に含まれない値を取得
fn get_no_used_value(n: usize, a: &Vec<i64>) -> HashSet<i64> {
let mut non_used = HashSet::new();
for i in 1..=n { non_used.insert(i as i64); }
for &aa in a {
if aa == -1 { continue; }
non_used.remove(&aa);
}
non_used
}
ABC425-C
問題
数列
解説
問題の通りに数列を操作して区間和を計算すると、計算量が
そのため、効率的に処理する方法を考えます。
- 数列の回転を効率化する
数列の先頭を末尾に移動する操作を実際に行うのではなく、「現在の先頭がどこにあるか」を記録します。
これにより、数列全体を操作する必要がなくなります。 - 累積和を利用する
区間和を効率的に計算するために、累積和を事前に計算しておきます。
累積和を使うと、区間[l..r] S[r] - S[l-1]
このl r - 数列を2周分用意する
2で先頭の位置をずらして読むと、インデックスが配列の末尾を超える場合があります。
これを回避するために、数列を2倍に複製して累積和を計算します。
これにより、どのような回転や区間指定にも対応できます。
この1から3の工夫を行うことで、計算量は
コード
abc425c.rs
use proconio::input;
fn main() {
// 入力
input! {
n: usize, // 数列の長さ
q: usize, // クエリ数
a: [usize; n], // 数列の値
}
// 数列を2周分にして累積和を計算
let acc_double = calc_double_acc(n, &a);
// 現在の回転位置
let mut rotate_pos = 0;
// クエリ処理
for _ in 0..q {
input! {
nm: usize, // クエリ番号
}
if nm == 1 {
// 回転操作
input! {
c: usize, // 右にずらす個数
}
rotate_pos = (rotate_pos + c) % n;
} else {
// 区間和計算
input! {
l: usize, r: usize, // 区間[l..r] (1-indexed)
}
let l_idx = l + rotate_pos - 1;
let r_idx = r + rotate_pos;
let ans = acc_double[r_idx] - acc_double[l_idx];
println!("{}", ans);
}
}
}
// 数列を2周分にして累積和を計算する関数
fn calc_double_acc(n: usize, a: &Vec<usize>) -> Vec<usize> {
let double_sz = 2 * n;
let mut acc_double = vec![0; double_sz + 1];
// 数列を2周分作成
let mut a_double = a.clone();
for &aa in a {
a_double.push(aa);
}
// 累積和を計算
for i in 0..double_sz {
acc_double[i + 1] = acc_double[i] + a_double[i];
}
acc_double
}
ABC425-D
問題
これは、与えられたマス目において、特定のルールに従って白マスを黒マスに変換し、最終的な黒マスの個数を求める問題です。
解説
この問題では、各白マスについて、上下左右の隣接するマスに黒マスが1つだけ存在する場合、その白マスを黒マスに変換します。
この操作はすべてのマスに対して同時に行われます。
そのため、黒マスへ置き換えができるマスを一度記録しておき、まとめて置き換えを行えばよいです。
次に、黒マスに変換可能な白マスを効率的に探索するために、幅優先探索（BFS）を用います。
初期状態で黒マスに隣接する白マスをキューに追加し、順次処理を進めます。
探索の流れとしては、以下の通りです。
- キューから白マスを取り出し、その白マスが黒マスに変換可能かを判定します。これをキューから取り出した白マス全てに対して実施します。
- 置き換え可能と判定した白マスを全て黒マスに変換します。その後、今置き換えた全ての黒マスについて、その周囲の白マスをキューに追加します。
- 一度チェックしたマスは再度チェックしないように管理します。
全ての操作が終了した後、マス目全体を走査して黒マスの個数を数えます。
コード
abc425d.rs
use std::collections::{HashSet, VecDeque};
use proconio::{input, marker::Chars};
// 上下左右の移動を表す定数
const D: [Pos; 4] = [Pos{x:!0, y:0}, Pos{x:0, y:!0}, Pos{x:1, y:0}, Pos{x:0, y:1}];
// 座標を表す構造体
#[derive(PartialEq, Eq, PartialOrd, Ord, Hash, Clone)]
struct Pos {
x: usize,
y: usize,
}
fn main() {
// 入力
input! {
h: usize, w: usize, // 縦と横のサイズ
mut s: [Chars; h], // マス目
}
// 白→黒への塗り替えをBFSで実施
bfs(h, w, &mut s);
// 黒マスの個数を数えて出力
let mut ans = 0;
for i in 0..h {
for j in 0..w {
if s[i][j] == '#' {
ans += 1;
}
}
}
println!("{}", ans);
}
// 幅優先探索 (BFS) を用いて白マスを黒マスに変換
fn bfs(h: usize, w: usize, s: &mut Vec<Vec<char>>) {
// キューの初期化 (黒マスの上下左右の白マスをキューに追加)
let mut dq = VecDeque::new();
init_dq(h, w, s, &mut dq);
// チェックした座標を管理
let mut seen = vec![vec![false; w]; h];
// キューがなくなるまで実施
while dq.len() > 0 {
// 各白マスについて、上下左右のうち1マスだけ黒マスである座標集合を取得
let paint_st = get_paint_set(h, w, s, &mut dq, &mut seen);
// 座標集合に対して以下を実施
for Pos { x: cx, y: cy } in paint_st {
// 黒マスに塗り替え
s[cx][cy] = '#';
// 上下左右にある白マスをキューに追加
push_dq(h, w, cx, cy, s, &mut dq);
}
}
}
// 初期状態で黒マスに隣接する白マスをキューに追加
fn init_dq(h: usize, w: usize, s: &mut Vec<Vec<char>>, dq: &mut VecDeque<Pos>) {
for cx in 0..h {
for cy in 0..w {
// 黒マスを見つける
if s[cx][cy] == '#' {
// 上下左右にある白マスをキューに追加
push_dq(h, w, cx, cy, s, dq);
}
}
}
}
// 指定した座標の上下左右の白マスをキューに追加
fn push_dq(h: usize, w: usize, cx: usize, cy: usize, s: &Vec<Vec<char>>, dq: &mut VecDeque<Pos>) {
for d in D {
let nx = cx.wrapping_add(d.x);
let ny = cy.wrapping_add(d.y);
if nx >= h || ny >= w { continue; }
if s[nx][ny] == '.' {
dq.push_back(Pos { x: nx, y: ny });
}
}
}
// キューにある白マスを調べ、黒マスに変換可能な座標集合を取得
fn get_paint_set(
h: usize, w: usize,
s: &Vec<Vec<char>>, dq: &mut VecDeque<Pos>,
seen: &mut Vec<Vec<bool>>,
) -> HashSet<Pos> {
let mut st = HashSet::new();
while let Some(Pos { x: cx, y: cy }) = dq.pop_front() {
if seen[cx][cy] { continue; }
seen[cx][cy] = true;
let cnt = calc_black_cnt(h, w, cx, cy, s);
if cnt == 1 {
st.insert(Pos { x: cx, y: cy });
}
}
st
}
// 指定した座標の上下左右にある黒マスの個数を計算
fn calc_black_cnt(h: usize, w: usize, cx: usize, cy: usize, s: &Vec<Vec<char>>) -> usize {
let mut cnt = 0;
for d in D {
let nx = cx.wrapping_add(d.x);
let ny = cy.wrapping_add(d.y);
if nx >= h || ny >= w { continue; }
if s[nx][ny] == '#' {
cnt += 1;
}
}
cnt
}
ABC425-E
問題
並べ方の総数が非常に大きくなる可能性があるため、結果を
解説
上記の式を直接計算するのは困難なため、ボールを1種類ずつ順番に配置していきながら並べ方の総数を計算します。
- 1種類目のボールは1通りの配置しかありません。
- 2種類目以降のボールを配置する際には、既に配置したボールの数と新たに配置するボールの数を用いて二項係数を計算します。
例えば、2種類目のボールを配置する場合、\binom{C_1 + C_2}{C_2}
また、二項係数
ここでは、パスカルの三角形を用いて二項係数を事前計算します。これにより、効率的に二項係数を求めることができます。
コード
abc425e.rs
use proconio::input;
const MAX_SZ: usize = 5000;
fn main() {
// 入力
input! {
t: usize, // テストケース数
m: usize, // 剰余の値
}
// パスカルの三角形を用いて、二項係数を事前計算
let mut comb = CalcCombPascal::new(MAX_SZ, m);
comb.pre_exe();
for _ in 0..t {
solve(&mut comb, m);
}
}
fn solve(comb: &mut CalcCombPascal, m: usize) {
input! {
n: usize, // 種類数
c: [usize; n], // 各種類のボールの個数
}
// 合計の個数
let mut tot_cnt = c[0];
// 1種類目の並べ方の総数
let mut ans = 1;
// 2種類目以降の並べ方の総数を順番に計算
for i in 1..n {
let val = comb.get_comb(tot_cnt + c[i], c[i]);
ans = ans * val % m;
tot_cnt += c[i];
}
// 答えを出力
println!("{}", ans);
}
struct CalcCombPascal {
n: usize,
comb: Vec<Vec<usize>>,
mods: usize,
}
impl CalcCombPascal {
// 初期化+パスカルの三角形
pub fn new(n: usize, mods: usize) -> Self {
let comb = vec![vec![0; n + 1]; n + 1];
CalcCombPascal { n, comb, mods }
}
// パスカルの三角形を計算
pub fn pre_exe(&mut self) {
self.comb[0][0] = 1;
for i in 0..self.n {
for j in 0..=self.n {
self.comb[i + 1][j] += self.comb[i][j];
if j > 0 {
self.comb[i + 1][j] += self.comb[i][j - 1];
}
self.comb[i + 1][j] %= self.mods;
}
}
}
// 組み合わせの値を返す
pub fn get_comb(&mut self, n: usize, r: usize) -> usize {
if n > self.n {
return 0;
}
self.comb[n][r]
}
}
ABC425-F
問題
空文字列から順番に文字を挿入して文字列
解説
文字列
このように逆算したうえで、動的計画法 (DP) を用いて効率的に解を求めることができます。
DPの状態と遷移は以下のように定義します。
-
状態
-
DP[\text{cstate}] -
\text{cstate}
-
-
遷移
- 現在の状態
\text{cstate} T b
\text{nstate ← cstate} \oplus (1 << b)
- 現在の状態
ただし、同じ文字が連続している箇所から削除する場合は、削除する文字を区別しないようにする必要があります。
これを実現するために、直前に削除した文字を記録し、同じ文字が連続している場合はスキップします。
コード
abc425f.rs
use proconio::{input, marker::Chars};
const MOD: usize = 998244353;
fn main() {
// 入力
input! {
n: usize, // 文字列の長さ
t: Chars, // 全て並べた後の文字列
}
// 状態数
let sz = 1 << n;
// DP[文字列Tの文字の状態] = その状態を満たす組み合わせ数
let mut dp = vec![0; sz];
dp[sz - 1] = 1; // 全ての文字が残っている状態からスタート
// 各状態を後ろから調べる
for cstate in (0..sz).rev() {
// 直前の文字を初期化
let mut prev_char = '?';
// 削除する文字を選ぶ
for b in 0..n {
// 削除済みの文字に対しては処理しない
if cstate & (1 << b) == 0 {
continue;
}
// 直前の文字と異なるなら削除する
if prev_char != t[b] {
let nstate = cstate ^ (1 << b); // 次の状態を計算
dp[nstate] += dp[cstate]; // 遷移
dp[nstate] %= MOD; // MODで余りを取る
}
// 直前の文字を更新
prev_char = t[b];
}
}
// 全て削除後の組み合わせ数を出力
println!("{}", dp[0]);
}
Discussion