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

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

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

 ABC422-A問題
https://atcoder.jp/contests/abc422/tasks/abc422_a
入力で与えられたステージの、次のステージを求める問題です。
解説
この問題では、1つのワールドに8つのステージが存在するという設定になっています。(入力のステージは、 W-S 形式で与えられる)

したがって、次のステージを求めるには以下の通りに計算すればよいです。
現在のステージ番号が1から7の場合は、ステージ番号を1増やします。
現在のステージ番号が8の場合は、ワールド番号を1増やし、ステージ番号を1にリセットします。
コード
abc422a.rs
use proconio::{input, marker::Chars};

fn main() {
    // 入力
    input! {
        s: Chars, // ワールドとステージの文字列
    }

    // ワールドとステージの番号を取り出す
    let world = s[0] as u8 - 0x30;
    let stage = s[2] as u8 - 0x30;

    // 次のステージを求める
    if stage == 8 {
        println!("{}-{}", world + 1, 1);
    } else {
        println!("{}-{}", world, stage + 1);
    }
}

 ABC422-B問題
https://atcoder.jp/contests/abc422/tasks/abc422_b
ロープがループ構造になっているかどうかを判定する問題です。
解説
この問題では、マス目上に配置されたロープ（#）がループ構造の形状をしているかを判定します。ループ構造の形状をしているためには、各ロープマスが他のロープマスと適切に連結している必要があります。

具体的には、各ロープマスの上下左右4方向の隣接するマスがロープ（#）であるかを確認し、その個数が2個または4個であるかを調べていけばよいです。
コード
abc422b.rs
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}]; // 上左下右

#[allow(unused)]
#[derive(Clone)]
struct Pos {
    x: usize,
    y: usize,
}

fn main() {
    // 入力
    input! {
        h: usize, // マス目の縦の長さ
        w: usize, // マス目の横の長さ
        s: [Chars; h], // マス目の情報
    }

    for i in 0..h {
        for j in 0..w {
            // ロープがないマスはチェック不要
            if s[i][j] == '.' { continue; }

            // ロープがあるマスの場合は、
            // 周囲に2個または4個、連結部分があるかをチェック
            if !is_correct(h, w, i, j, &s) {
                println!("No");
                return;
            }
        }
    }

    println!("Yes");
}

fn is_correct(
    h: usize, w: usize, 
    x: usize, y: usize,
    s: &Vec<Vec<char>>
) -> bool {
    let mut rope_cnt = 0;

    // 4方向チェック
    for d in D {
        // 隣のマス
        let nx = x.wrapping_add(d.x);
        let ny = y.wrapping_add(d.y);

        // 隣のマスが範囲外の場合は見ない
        if nx >= h || ny >= w { continue; }
        // 隣のマスがロープでない場合は見ない
        if s[nx][ny] == '.' { continue; }

        // ロープの個数をカウント
        rope_cnt += 1;
    }

    // 2個または4個ならOK
    rope_cnt == 2 || rope_cnt == 4
}

 ABC422-C問題
https://atcoder.jp/contests/abc422/tasks/abc422_c
「A と C の文字を1つずつ、A , B , C から文字を1つ」の計3文字で文字列を作るとき、最大で何個の文字列を作れるかを求める問題です。
解説
作れる文字列の個数を x と仮定します。以下1~3の条件を全て満たすかどうかを確認します。

A を x 個使えるか。

C を x 個使えるか。
残った A と C 、および B を組み合わせて x 個使えるか。
x は一定の値を超えると条件を満たさなくなるため、単調性があります。このため、二分探索を用いると効率的に求められます。
コード
use proconio::input;
const MAX_SZ: i64 = 1_000_000_000;

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

fn solve() {
    input! {
        a: i64, b: i64, c: i64 // A, B, C の個数
    }

    // 答えを二分探索
    let mut ok = -1;
    let mut ng = MAX_SZ + 1;
    for _ in 0..50 {
        let mid = (ok + ng) / 2;

        if is_enable(a, b, c, mid) {
            ok = mid;
        } else {
            ng = mid;
        }
    }
    
    // 答えを出力
    println!("{}", ok);
}

fn is_enable(a: i64, b: i64, c: i64, x: i64) -> bool {
    // A, C の個数が x 未満なら条件を満たさない
    if a < x { return false; }
    if c < x { return false; }

    // A と C の余りの個数を計算
    let rest_a = a - x;
    let rest_c = c - x;

    // 余りの合計個数 + B の個数が x 以上であれば条件を満たす
    rest_a + b + rest_c >= x
}

 ABC422-D問題
https://atcoder.jp/contests/abc422/tasks/abc422_d
総和 K から長さ 2^N の数列を作る際に、数列の値のばらつきが小さくなるような数列を作る問題です。
解説
この問題は再帰を用いることで解くことができます。

具体的には、以下のように再帰的に調べます。
長さが1の場合は、その位置に総和の値をセットします。
長さが2以上の場合は、総和と長さを2分割したうえで、左半分と右半分をそれぞれ再帰的に処理します。
数列が完成した後、その数列の最大値と最小値を用いてばらつき度（最大値 - 最小値）を求めます。この方法により、総和を均等に分割しながら数列を構築することで、ばらつきが最小になるような数列を作成できます。
コード
abc422d.rs
use itertools::Itertools;
use proconio::input;

fn main() {
    // 入力
    input! {
        n: usize, // 操作回数
        k: usize, // 総和
    }

    // 数列の長さ
    let sz = 1 << n;

    // 答えの数列を初期化
    let mut arr = vec![0; sz];

    // 再帰を用いて答えを求める
    rec(sz, 0, k, &mut arr);

    // アンバランス度(数列のmax-min)の出力
    let val_max = *arr.iter().max().unwrap();
    let val_min = *arr.iter().min().unwrap();
    println!("{}", val_max - val_min);

    // 答えの数列の出力
    println!("{}", arr.iter().join(" "));
}

fn rec(
    cur_sz: usize, // 今の長さ
    cur_spos: usize, // 今の先頭index
    cur_k: usize, // 今の総和の値
    arr: &mut Vec<usize>, // 答えの数列
) {
    // 長さが1なら、値をセット
    if cur_sz == 1 {
        arr[cur_spos] = cur_k;
        return;
    }
    // 長さが2以上なら、分割して左半分右半分を再帰的に調べる

    let half_sz = cur_sz / 2;

    let left_spos = cur_spos;
    let right_spos = cur_spos + cur_sz / 2;

    let left_k = cur_k / 2;
    let right_k = cur_k - left_k;
    
    rec(half_sz, left_spos, left_k, arr);
    rec(half_sz, right_spos, right_k, arr);
}

 ABC422-E問題
https://atcoder.jp/contests/abc422/tasks/abc422_e
N 個の点から任意の2点を選んで直線を作り、その直線が過半数の点を通る場合、その直線の方程式を求める問題です。
解説
過半数の点を通る直線が存在する条件を考えます。

この時、過半数の点を通る直線が存在する場合のその直線上にある点の集合を t とします。

N 個の点から選んだ2点が、2点とも集合 t に含まれる確率は、

\begin{aligned}
\frac{{}_t C_2}{{}_N C_2}
\end{aligned}
となります。ここで、t は過半数を超える最小の値

\begin{aligned}
t = \frac{N+1}{2}
\end{aligned}
として代入すると、

\begin{aligned}
\frac{{}_t C_2}{{}_N C_2} &= \frac{\frac{N+1}{2}}{N} \times \frac{\frac{N+1}{2}-1}{N-1} \\
&= \frac{(N+1)(N-1)}{4N(N-1)} \\
&= \frac{N+1}{4N} \\
&= \frac{1}{4} + \frac{1}{4N} \\
&> \frac{1}{4}
\end{aligned}
となり、 \frac{1}{4} 以上の確率であることが分かります。

よって、乱択アルゴリズムにより一定回数(100)程度繰り返して、

この条件を満たす直線が見つかれば、その直線の方程式を答えればよいです。
具体的には、以下1~3を繰り返して求めます。
点の集合からランダムに2点を選び、その2点を通る直線の方程式を求めます。
求めた直線上にある点の個数を数えます。
その個数が過半数を超えていれば、その直線の方程式を出力します。
もし一定回数試行しても条件を満たす直線が見つからない場合は、 No を出力します。
コード
abc422e.rs
use proconio::input;
use rand::Rng;

#[derive(Clone)]
struct Pos {
    x: i64,
    y: i64,
}

#[derive(Clone)]
struct StraightLine {
    a: i64,
    b: i64,
    c: i64,
}

fn main() {
    // 入力
    input! {
        n: usize, // 点の数
        xy: [(i64, i64); n], // 点の座標
    }

    let mut rng = rand::thread_rng();
    for _ in 0..100 {
        // 異なる2点を選ぶ
        let i = rng.gen_range(0..n);
        let j = rng.gen_range(0..n);
        if i == j { continue; }
        
        // 直線の方程式を求める
        let straight = calc_equation_straight_line(
            Pos {x: xy[i].0, y: xy[i].1}, 
            Pos {x: xy[j].0, y: xy[j].1});

        // 同一直線状にある点の個数を求める
        let mut cnt = 0;
        for k in 0..n {
            if is_same_straight_line(Pos {x: xy[k].0, y: xy[k].1}, &straight) {
                cnt += 1;
            }
        }

        // 点の個数が過半数を超えていたら、その直線の方程式を出力
        if cnt > n / 2 {
            println!("Yes");
            println!("{} {} {}", straight.a, straight.b, straight.c);
            return;
        }
    }

    // 条件を満たす直線の方程式なし
    println!("No");
}

// 2点から、直線の方程式(ax+by+c=0)を求める
fn calc_equation_straight_line(i: Pos, j: Pos) -> StraightLine {
    let a = -(i.y - j.y);
    let b = i.x - j.x;
    let c = i.y * j.x - i.x * j.y;

    StraightLine {a, b, c}
}
// 同一直線上にある点かどうかを判定
fn is_same_straight_line(i: Pos, line: &StraightLine) -> bool {
    line.a * i.x + line.b * i.y + line.c == 0
}
ABC422-A

ABC422-B

ABC422-C

ABC422-D

ABC422-E

Discussion
