緑コーダーがRustで解説してみた(ABC428 A～E)

AtCoder Beginner Contest 428のA～E問題を緑コーダーが自分なりの解説と解答コードをまとめました。
参考になりましたら幸いです。

ABC428-A

問題

https://atcoder.jp/contests/abc428/tasks/abc428_a

走る動作 $A$ 秒と停止動作 $B$ 秒を交互に、合計 $X$ 秒行ったとき、何メートル走るのかを求める問題です。

解説

この問題では、走る動作と停止動作を1つのサイクルとして考えます。
1つのサイクルは $(A + B)$ 秒間で構成されます。
そして、$X$ 秒後の状態を、サイクルの繰り返し回数 $T$ と、サイクル内の残り時間 $U$ に分解して考えます。

具体的な解法は1.から4.の通りです。

1. サイクルの計算
   $X$ 秒を $(A + B)$ 秒のサイクルで割り算し、商を $T$（サイクルの回数）、余りを $U$（サイクル内の残り時間）とします。
   式は次のようになります。
   $X = (A + B) \times T + U$

2. サイクル部分の距離計算
   サイクル部分では、1サイクル内で $A$ 秒間走る動作を $T$ 回繰り返します。
   この区間の合計距離は $S \times A \times T$ です。

3. 残り時間部分の距離計算
   残り時間 $U$ 秒については、$A$ 秒間走る動作の範囲内であれば $U$ 秒間走り、それを超える場合は $A$ 秒間だけ走ります。
   この区間の合計距離は $S \times \min(A, U)$ です。

4. 合計距離の計算
   サイクル部分と残り時間部分の距離を足し合わせて、最終的な移動距離を求めます。

コード

abc428a.rs

use proconio::input;
use std::cmp::min;

fn main() {
    // 入力
    input! {
        s: usize, // 移動時の秒速
        a: usize, // 続けて走る秒数
        b: usize, // 走った後停止する秒数
        x: usize, // 移動秒数
    }

    let mut ans = 0;

    // x秒間の操作を、(a+b)秒のサイクルとステップに分ける。
    let t = x / (a + b); // サイクルの回数
    let u = x % (a + b); // サイクル内の残り時間

    // サイクル分は、秒速sでa秒間の移動をt回行う
    ans += s * a * t;

    // ステップ分は、秒速sで最大a秒間移動する
    ans += s * min(u, a);

    // 合計の移動距離を出力
    println!("{}", ans);
}

ABC428-B

問題

https://atcoder.jp/contests/abc428/tasks/abc428_b

長さ $N$ の文字列 $S$ について、考えられる長さ $K$ の部分文字列を全て作成し、その中で出現回数が最も多い文字列を全て出力する問題です。

解説

以下、1.から5.の順に処理していくことで解くことができます。

1. 部分文字列の作成
   長さ $K$ の部分文字列を作成します。
   具体的には、文字列 $S$ の先頭から $K$ 文字を切り取った部分文字列、次に2番目の文字から $K$ 文字を切り取った部分文字列、といった具合に、$N-K+1$ 個の部分文字列を作成します。

2. 出現回数の計算
   作成した部分文字列を連想配列（HashMap）を用いて管理します。
   この連想配列では、キーに部分文字列、値にその出現回数を格納します。

3. 最大出現回数の特定
   連想配列を調べ、出現回数の最大値を求めます。

4. 最大出現回数を持つ文字列の収集
   出現回数が最大値と一致する部分文字列を連想配列から抽出し、リストに格納します。
   このリストは昇順にソートしておきます。

5. 結果の出力
   出現回数の最大値と、それに対応する部分文字列を昇順で出力します。

コード

abc428b.rs

use proconio::{input, marker::Chars};
use std::collections::HashMap;
use std::cmp::max;

fn main() {
    // 入力
    input! {
        n: usize, // 文字列の長さ
        k: usize, // 部分文字列の長さ
        s: Chars, // 文字列
    }

    // n-k+1個の部分文字列を連想配列に格納
    let mp = make_string_map(n, k, &s);
    // 連想配列中の部分文字列の出現回数の最大値を取得
    let cnt = get_count_max_map(&mp);
    // 出現回数の最大値と一致する部分文字列を収集（昇順にソート）
    let str_list = collect_string(&mp, cnt);

    // 出現回数の最大値を出力
    println!("{}", cnt);
    // 部分文字列を順番に出力
    for item in &str_list {
        println!("{}", &item);
    }
}

// 部分文字列を作成し、連想配列に格納する関数
fn make_string_map(n: usize, k: usize, s: &Vec<char>) -> HashMap<String, usize> {
    let mut mp = HashMap::new();
    for i in 0..n - k + 1 {
        let mut ret = Vec::new();
        for j in 0..k {
            ret.push(s[i + j]);
        }
        let str: String = ret.iter().collect();
        *mp.entry(str).or_insert(0) += 1;
    }
    mp
}

// 連想配列中の出現回数の最大値を取得する関数
fn get_count_max_map(mp: &HashMap<String, usize>) -> usize {
    let mut cnt = 0;
    for (_k, &v) in mp {
        cnt = max(cnt, v);
    }
    cnt
}

// 出現回数が最大値の部分文字列を収集する関数
fn collect_string(mp: &HashMap<String, usize>, cnt: usize) -> Vec<String> {
    let mut ret = Vec::new();
    for (k, &v) in mp {
        if v == cnt {
            ret.push(k.clone());
        }
    }
    // 昇順にソート
    ret.sort();
    ret
}

ABC428-C

問題

https://atcoder.jp/contests/abc428/tasks/abc428_c

括弧列に対して文字を追加または削除する操作を行った後、その状態が「良い括弧列」であるかを判定する問題です。

良い括弧列の条件

1. '(' と ')' の数が一致している。
2. 文字列を左から順に見たとき、どの時点でも '(' の数が ')' の数以上である。

解説

括弧列の状態を効率的に管理し、良い括弧列かどうかを判定するために以下1.から2.の工夫を行います。

1. 状態を数値で管理する

   • '(' を +1、')' を -1 として数値化し、現在の状態を status という変数で管理します。
   • 文字を追加する場合は、status に +1 または -1 を加算します。
   • 文字を削除する場合は、status に +1 または -1 を減算します。
   • このようにすることで、括弧の数が一致しているかを効率的に判定できます。

2. 途中で ')' が '(' を上回るかの判定

   • 途中で status が 0未満になる場合、')' が '(' を上回ったことを意味します。
   • この情報を管理するために、NG回数 を記録します。
     • 文字を追加後に status が 0未満になった場合、NG回数 を増やします。
     • 文字を削除前に status が 0未満だった場合、NG回数 を減らします。
   • NG回数 が 0 であれば、')' が '(' を上回っていないことが保証されます。

クエリごとに、status が 0 かつ NG回数 が 0 であれば Yes を出力し、そうでなければ No を出力します。

コード

abc428c.rs

use proconio::input;

fn main() {
    // 入力
    input! {
        q: usize, // クエリ数
    }

    // 括弧列状態のスタック
    let mut brackets_stack = Vec::new();
    // 括弧列状態 (は+1、)は-1として数える
    let mut status = 0;
    // NG回数を管理
    let mut ng_cnt = 0;

    // クエリ処理
    for _ in 0..q {
        input! {
            nm: usize,
        }
        if nm == 1 {
            input! {
                c: char,
            }
            // 括弧列のスタックを追加
            brackets_stack.push(c);
            // ステータス更新
            update_status(c, true, &mut status);
            // 0未満になったらNG回数を1増やす
            if status < 0 { ng_cnt += 1; }
        } else {
            // 括弧列のスタックを取り出し
            let c = brackets_stack.pop().unwrap();
            // 0未満で操作されたらNG回数を1減らす
            if status < 0 { ng_cnt -= 1; }
            // ステータス更新
            update_status(c, false, &mut status);
        }
        // ステータスが0、NG回数が0ならYes
        println!("{}", if status == 0 && ng_cnt == 0 { "Yes" } else { "No" });
    }
}

// ステータスを更新する関数
fn update_status(c: char, is_push: bool, status: &mut i32) {
    if (c == '(' && is_push) || (c == ')' && !is_push) {
        *status += 1;
    } else {
        *status -= 1;
    }
}

ABC428-D

問題

https://atcoder.jp/contests/abc428/tasks/abc428_d

平方数の個数を求める問題です。

解説

$C+X$ の桁数ごとにグループ化し、それぞれのグループ内で平方数の個数を調べることで解くことができます。
具体的には、以下1.から3.の順に考えていきます。

1. 桁数ごとにグループ化
   $C+X$ の桁数が同じであれば、$f(C, C+X)$ の桁数も同じで連続した値になります。
   そのため、$C+X$ の桁数ごとにグループ化して考えることができます。

2. グループ内の範囲を特定
   $C+X$ の桁数を $K$ とした場合、$C+X$ の最小値 $L$ と最大値 $R$ を特定します。
   この範囲内で $X$ が $1 \leq X \leq D$ を満たすように調整します。

3. 平方数の個数を計算
   $f(C, C+X)$ の値が平方数である個数を求めます。
   これは累積和の要領で、$\sqrt{f(C, C+R)} - \sqrt{f(C, C+L) - 1}$ によって計算できます。

これを$f(C, C+X)$ の制約の中で考えられる桁数(1～10)について全て調べ、平方数の個数を合計します。

コード

abc428d.rs

use proconio::input;
use std::cmp::{min, max};
use num::integer::sqrt;

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

const SZ: usize = 10;

fn solve() {
    input! {
        c: i64, d: i64, // 値c, d
    }

    // 10のべき乗を事前計算
    let multi10 = calc_multi10(SZ);

    // 答えの個数
    let mut ans = 0;

    // (c+x)を桁毎に数える
    for digit in 1..=SZ {
        // min < c+x < maxを満たすxを求める
        let (min_x, max_x) = calc_equation_min_max(multi10[digit], c, d);
        
        // 大小が逆転している場合は無視
        if min_x > max_x { continue; }
        
        // f(c, c+x)の値を取得
        let func_min = get_func_c(c, multi10[digit], min_x);
        let func_max = get_func_c(c, multi10[digit], max_x);
        
        // [min..max]の平方数の個数を求める
        ans += sqrt(func_max) - sqrt(func_min - 1);
    }

    // 個数を出力
    println!("{}", ans);
}

// 10のべき乗を計算
fn calc_multi10(sz: usize) -> Vec<i64> {
    let mut multi10 = vec![1i64; sz + 1];
    for i in 0..sz {
        multi10[i + 1] = multi10[i] * 10;    
    }
    multi10
}

// min_x と max_x を計算
fn calc_equation_min_max(multi: i64, c: i64, d: i64) -> (i64, i64) {
    // 1以上、10^桁数における最小値-c
    let min_x = max(1, multi / 10 - c);
    // d以下、10^桁数における最大値-c
    let max_x = min(d, multi - 1 - c);

    (min_x, max_x)
}

// f(c, c+x) を計算
fn get_func_c(c: i64, multi: i64, x: i64) -> i64 {
    (c * multi) + (c + x)
}

ABC428-E

問題

https://atcoder.jp/contests/abc428/tasks/abc428_e

$N$ 頂点の木における各頂点から最も遠い頂点を求める問題です。

解説

木の距離を求める際には、「木の直径」という概念を活用します。
木の直径とは、木の中で最も長いパスの長さを指します。
この問題では、木の直径を求める過程で得られる情報を利用して、各頂点から最も遠い頂点を効率的に求めます。
具体的には、幅優先探索（BFS）を3回行うことで解を導きます。

1. 1回目のBFS
   適当な頂点（例えば頂点0）から探索を開始し、最も遠い頂点（$S1$）を特定します。
   この頂点が $N$ 頂点の木における根(端の頂点)になります。

2. 2回目のBFS
   頂点 $S1$ から探索を開始し、最も遠い頂点（$S2$）を特定します。
   このとき、$S1$ から各頂点への最短距離も記録します。

3. 3回目のBFS
   頂点 $S2$ から探索を開始し、$S2$ から各頂点への最短距離を記録します。

最後に、各頂点について、2回目と3回目のBFSで得られた距離を比較し、最も遠い頂点を求めます。

コード

abc428e.rs

use proconio::{input, marker::Usize1};
use std::collections::VecDeque;
const INF: usize = 1 << 60;

#[derive(PartialEq, Eq, PartialOrd, Ord, Hash, Clone)]
struct LongInfo {
    long_dist: usize, // 最長距離
    long_pos: usize,  // 最長距離時の頂点
}

fn main() {
    input! {
        n: usize, // 頂点数
    }

    // 無向グラフ構築
    let graph = make_graph(n);

    // 開始座標
    let mut cur = 0;
    // 各頂点の最長距離とその座標
    let mut ans = vec![LongInfo { long_dist: 0, long_pos: 0 }; n];
    
    // BFSを3回行う
    for _ in 0..3 {
        // 最短距離情報
        let mut min_dist = vec![INF; n];
        let next_pos = bfs(n, cur, &graph, &mut min_dist);
        
        // 各頂点の(最長距離, 座標)を更新
        for idx in 0..n {
            if ans[idx].long_dist < min_dist[idx] || 
               (ans[idx].long_dist == min_dist[idx] && ans[idx].long_pos < cur) {
                ans[idx].long_dist = min_dist[idx];
                ans[idx].long_pos = cur;
            }
        }
        cur = next_pos;
    }

    // 各頂点の最も遠い座標を出力
    for info in &ans {
        println!("{}", info.long_pos + 1);
    }
}

fn make_graph(n: usize) -> Vec<Vec<usize>> {
    let mut graph = vec![Vec::new(); n];
    for _ in 0..n - 1 {
        input! {
            u: Usize1, v: Usize1, // 頂点u, v (0-indexed)
        }
        graph[u].push(v);
        graph[v].push(u);
    }
    graph
}

fn bfs(n: usize, start: usize, graph: &Vec<Vec<usize>>, min_dist: &mut Vec<usize>) -> usize {
    // 最短距離初期化
    min_dist[start] = 0;
    // 調べる座標のキュー初期化
    let mut dq = VecDeque::new();
    dq.push_back(start);

    // 頂点を調べる
    while let Some(cur) = dq.pop_front() {
        for &next in &graph[cur] {
            if min_dist[next] == INF {
                min_dist[next] = min_dist[cur] + 1;
                dq.push_back(next);
            }
        }
    }

    // 最も遠い頂点を見つけて返す
    let mut long_dist = 0;
    let mut ret_pos = 0;
    for i in (0..n).rev() {
        if long_dist < min_dist[i] {
            long_dist = min_dist[i];
            ret_pos = i;
        }
    }
    ret_pos
}