👨‍🍳
緑コーダーがRustで解説してみた(ABC430 A～E)

2025/11/02に公開
AtCoder Beginner Contest 430のA～E問題を緑コーダーが自分なりの解説と解答コードをまとめました。

参考になりましたら幸いです。

 ABC430-A問題
https://atcoder.jp/contests/abc430/tasks/abc430_a
飴とクッキーの所持数が条件に違反しているかを判定する問題です。
解説
以下の条件の違反有無を判定します。
飴を A 個以上所持している場合、クッキーを B 個以上所持していなければならない。
条件を整理すると、以下の表の通りになります。


飴の所持数
クッキーの所持数
違反有無



A 個以上

B 個以上
違反しない


A 個以上

B 個未満
違反する


A 個未満

B 個以上
違反しない


A 個未満

B 個未満
違反しない

上記の表より、飴の所持数が A 個以上で、かつクッキーの所持数が B 個未満の場合に「違反」となります。

違反しているなら Yes 、そうでないなら No を出力します。
コード
abc430a.rs
use proconio::input;

fn main() {
    input! {
        a: usize, // 条件の飴の個数
        b: usize, // 条件のクッキーの個数
        c: usize, // 所持している飴の個数
        d: usize, // 所持しているクッキーの個数
    }

    // 飴がa個以上かつクッキーがb個未満の場合は違反
    if c >= a && d < b {
        println!("Yes");
    } else {
        println!("No");
    }
}

 ABC430-B問題
https://atcoder.jp/contests/abc430/tasks/abc430_b
N \times N の正方形のグリッドから M \times M の正方形のグリッドを切り出し、その形の種類数を求める問題です。
解説
M \times M のグリッドを切り出すために、元のグリッドの左上の座標 (i, j) を全て試します。

この時の左上の座標の範囲は、0 \leq (i, j) < N - M+1 となります。

各左上の座標から M \times M の部分グリッドを切り出し、それを集合（HashSet）に格納します。

HashSet は重複を許さないため、同じ形のグリッドは1つだけ格納されます。

集合に格納された要素の個数が、異なるグリッドの形の種類数となります。
コード
abc430b.rs
use proconio::{input, marker::Chars};
use std::collections::HashSet;

#[derive(PartialEq, Eq, PartialOrd, Ord, Hash, Clone)]
struct Pos {
    x: usize,
    y: usize,
}

fn main() {
    input! {
        n: usize, // グリッドの縦横サイズ
        m: usize, // 取り出すグリッドの縦横サイズ
        s: [Chars; n], // グリッド情報
    }

    // 取り出したグリッドの種類を管理
    let mut st = HashSet::new();

    // 調べるグリッドの範囲 (開始を左上で固定)
    let sz = n - m + 1;
    
    // グリッドの開始位置を全探索
    for i in 0..sz {
        for j in 0..sz {
            // 取り出したグリッドを格納
            let grid = take_out_grid(m, &s, Pos {x: i, y: j});
            st.insert(grid);
        }
    }

    // グリッドの種類数を出力
    println!("{}", st.len());
}

// 指定された位置から M × M のグリッドを切り出す関数
fn take_out_grid(m: usize, s: &Vec<Vec<char>>, pos: Pos) -> Vec<Vec<char>> {
    let mut ret = vec![vec!['.'; m]; m];
    for i in 0..m {
        for j in 0..m {
            ret[i][j] = s[i + pos.x][j + pos.y];
        }
    }
    ret
}

 ABC430-C問題
https://atcoder.jp/contests/abc430/tasks/abc430_c
トラック運転手が運転時間と休憩時間の条件に違反する (l, r) の組の個数を求める問題です。
解説
問題文の条件を以下のように分解します。
運転時間が A 分以上である。
休憩時間が B 分未満である。
運転開始位置を l、運転終了位置を r として、区間 [l, r) 内での運転時間と休憩時間を数え、

上記の条件を満たす組み合わせを数えます。
しかし、全ての区間を全探索すると計算量が O(N^2) となり、実行時間制限以内に解くことができません。

そのため、以下1.から3.の工夫を行います。
累積和の利用
運転時間を表す文字 'a' の累積和 acc_a を計算します。
休憩時間を表す文字 'b' の累積和 acc_b を計算します。
累積和を使うことで、任意の区間の運転時間や休憩時間を O(1) で計算できます。
二分探索の利用
運転開始位置 l を固定したとき、条件1を満たす最小の位置 apos を二分探索で求めます。
同様に、条件2を満たさなくなる最小の位置 bpos を二分探索で求めます。
これにより、条件を満たす区間の個数を効率的に計算できます。
全体の計算
運転開始位置 l を全探索し、各位置について条件を満たす区間の個数を計算して合計します。
二分探索を用いると、各位置の計算量は O(\log N) となります。

これにより、全体の計算量は O(N \log N) となり、実行時間制限以内に解くことができます。
コード
abc430c.rs
use std::cmp::max;
use proconio::{input, marker::Chars};

fn main() {
    input! {
        n: usize, // 文字列の長さ
        a: usize, // 運転時間
        b: usize, // 休憩時間
        s: Chars, // 文字列
    }

    // 運転時間('a')と休憩時間('b')の累積和を計算
    let acc_a = calc_acc_cnt(n, &s, 'a');
    let acc_b = calc_acc_cnt(n, &s, 'b');

    let mut ans = 0;
    
    // 運転開始位置を全探索
    for lpos in 0..n {
        // 条件1: 運転時間がA分以上になる最小位置を取得
        let apos = lower_bound(&acc_a, acc_a[lpos] + a);
        // 条件2: 休憩時間がB分以上になる最小位置を取得
        let bpos = lower_bound(&acc_b, acc_b[lpos] + b);
        // 条件を満たす区間の個数を計算
        ans += max(bpos as i64 - apos as i64, 0);
    }

    // 答えを出力
    println!("{}", ans);
}

// 累積和を計算する関数
fn calc_acc_cnt(n: usize, s: &Vec<char>, c: char) -> Vec<usize> {
    let mut acc_ret = vec![0; n+1];
    for i in 0..n {
        let add = if s[i] == c {1} else {0};
        acc_ret[i+1] += acc_ret[i] + add;
    }
    acc_ret
}

// 二分探索
// val以上の最小のposを返す 
pub fn lower_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;
        }
    }
    l
}


 ABC430-D問題
https://atcoder.jp/contests/abc430/tasks/abc430_d
各人について、最寄りの人の距離の総和を求める問題です。
解説
この問題では、各人を順番に追加していき、最寄りの人との距離の総和を効率的に計算する必要があります。

具体的には、以下の1.から4.の手順で解きます。
初期状態の計算

最初の2人について、距離の総和を計算します。

人0が地点0、人1が地点 X_1 の時の距離の総和は 2X_1 です。
差分更新

2人目以降を追加する際には、次のように差分を計算します
追加する人の前後にいる人の最寄りの距離を引きます。
追加する人を含む新しい最寄りの距離を足します。
順序付き集合（BTreeSet）を利用

各人の座標を順序付き集合に格納し、二分探索を用いて前後の人の座標を効率的に取得します。

これにより、計算量を削減できます。
番兵の利用

順序付き集合で前後の座標を取得する際、範囲外のエラーを防ぐために、

番兵として非常に大きな値と小さな値を追加します。
コード
abc430d.rs
use std::collections::BTreeSet;
use std::cmp::min;
use proconio::input;
const INF: i64 = 1 << 60;
fn main() {
    input! {
        n: usize, // 追加の人数
        x: [i64; n], // 追加される人の座標
    }

    // 順序付き集合で人の座標を管理
    let mut bst = BTreeSet::new();
    init_bset(&mut bst, &x);

    // 各人の最寄りの距離の総和(初期値)
    let mut ans = x[0] * 2;
    println!("{}", ans);

    // Aの2個目以降を処理
    for i in 1..n {        
        // 現在の位置
        let cur = x[i];

        // 現在の位置の前後を取得
        let (left, right) = get_lr_pos(cur, &bst);
        
        // 変更前の位置(後ろ、前)の最寄りの距離を引く
        ans -= calc_pos_dist(&vec![left, right], &bst);
        
        // 変更後の位置(後ろ、現在、前)の最寄りの距離を足す
        bst.insert(cur);
        ans += calc_pos_dist(&vec![left, cur, right], &bst);

        // 最寄りの距離の総和を出力
        println!("{}", ans);
    }
}

// 順序付き集合の初期化
fn init_bset(bst: &mut BTreeSet<i64>, x: &Vec<i64>) {
    // 番兵追加
    bst.insert(INF+1);
    bst.insert(INF);
    bst.insert(-INF);
    bst.insert(-INF-1);

    // 初期値追加
    bst.insert(0);
    bst.insert(x[0]);
}

// 現在の位置の前後の座標を取得
fn get_lr_pos(cur: i64, bst: &BTreeSet<i64>) -> (i64, i64){
    let next = *bst.range(cur+1..).next().unwrap();
    let prev = *bst.range(..=cur-1).next_back().unwrap();
    (prev, next)
}

// 指定された位置の最寄りの距離を計算
fn calc_pos_dist(pos: &Vec<i64>, bst: &BTreeSet<i64>) -> i64{
    let mut ret = 0;
    for &cpos in pos {
        if -INF < cpos && cpos < INF {
            let (prev, next) = get_lr_pos(cpos, bst);
            ret += min(cpos - prev , next - cpos);
        }
    }
    ret
}

 ABC430-E問題
https://atcoder.jp/contests/abc430/tasks/abc430_e
01文字列 A, B について、文字列 A の先頭を末尾に移動させる操作を繰り返すことで、文字列 B と一致させることができるかを判定する問題です。
解説
ローリングハッシュというアルゴリズムを使用することで解くことができます。

ローリングハッシュは、文字列の部分文字列を高速に比較するための手法で、文字列を数値（ハッシュ値）に変換し、その数値を比較することで文字列の一致判定を効率化します。
具体的には、以下1.から3.の通りに行うことで求めることができます。
文字列の準備:
文字列 A を2回繰り返して結合した文字列 A' を作成します。

これにより、A の先頭を末尾に移動させる操作をシミュレートできます。
ローリングハッシュの構築:
文字列 A' と B のハッシュ値を事前に計算します。
一致判定:

A の先頭を末尾に移動させる回数を 0 から |A|-1 まで試し、A' の部分文字列と B のハッシュ値を比較します。
一致する場合、その回数を出力します。一致しない場合は -1 を出力します。
コード
abc430e.rs
use proconio::{input, marker::Chars};

fn main() {
    // テストケース数の入力
    input!{
        t: usize,
    }
    for _ in 0..t {
        solve();
    }
}

fn solve() {
    input! {
        a: Chars, // 文字列a
        b: Chars, // 文字列b
    }
    let sz = a.len();

    // 文字列aを2つ繋げる
    let mut aa = a.clone();
    for &item in &a {
        aa.push(item);
    }

    // ローリングハッシュでハッシュ値を事前計算
    let roh_a = RollingHash::new(&aa);
    let roh_b = RollingHash::new(&b);

    // 先頭文字を末尾に移す回数を全探索
    for i in 0..sz {
        let val1 = roh_a.get_forward_hash(i+1, i+sz);
        let val2 = roh_b.get_forward_hash(1, sz);

        // 文字列が一致した場合は、末尾に移した回数を出力
        if val1 == val2 {
            println!("{}", i);
            return;
        }
    }

    // 全て試しても一致しない場合
    println!("-1");
}

// ローリングハッシュ
const HASH_MOD: usize = 2023464871;
const BASE : usize = 256;

struct RollingHash {
    power: Vec<usize>,              // 累乗 mod HASH_MOD
    forward_hash_values: Vec<usize>,// 先頭からの累積ハッシュ値
}

impl RollingHash {
    // 与えられた文字列 `s` からローリングハッシュを構築する。
    fn new(normal_s: &Vec<char>) -> Self {
        let n = normal_s.len();

        // 累乗を事前計算
        let power = Self::__calc_power(n);
        // 文字列のハッシュ値を前から計算
        let forward_hash_values = Self::__calc_hash_value_str(n, &normal_s);
        
        Self { power, forward_hash_values }
    }

    fn __calc_power(n: usize) -> Vec<usize>{
        let mut power = vec![1; n+1];
        for i in 0..n {
            power[i + 1] = power[i] * BASE % HASH_MOD;
        }
        power
    }

    fn __calc_hash_value_str(n: usize, s: &Vec<char>) -> Vec<usize> {
        let mut hash_values = vec![0; n + 1];
        for i in 0..n {
            hash_values[i + 1] = (hash_values[i] * BASE + (s[i] as usize)) % HASH_MOD;
        }
        hash_values
    }

    // 1-indexed で 累積ハッシュ値[l, r] の区間について前からのハッシュ値を取得する
    fn get_forward_hash(&self, l: usize, r: usize) -> usize {
        let from = l - 1;
        let to = r;
        let right = (self.forward_hash_values[to] + HASH_MOD) % HASH_MOD;
        let left = (self.power[to - from] * self.forward_hash_values[from]) % HASH_MOD;
        (right + HASH_MOD - left) % HASH_MOD
    }
}
飴の所持数	クッキーの所持数	違反有無
$A$ 個以上	$B$ 個以上	違反しない
$A$ 個以上	$B$ 個未満	違反する
$A$ 個未満	$B$ 個以上	違反しない
$A$ 個未満	$B$ 個未満	違反しない
ABC430-A

ABC430-B

ABC430-C

ABC430-D

ABC430-E

Discussion
