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

2025/08/11に公開
AtCoder Beginner Contest 418のA-E問題を緑コーダーが分かりやすく解説をまとめました。

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

 ABC418-A問題
https://atcoder.jp/contests/abc418/tasks/abc418_a
文字列 S が tea で終わるかどうかを判定する問題です。
解説
文字列 S の末尾3文字をスライスで取り出し、それが tea と一致するかどうかを確認します。一致する場合は Yes を、そうでない場合は No を出力します。
コード
abc418a.rs
use proconio::{input, marker::Chars};

fn main() {
    // 比較対象の文字列
    let cmp_str: Vec<char> = "tea".chars().collect();
    let cmp_sz = cmp_str.len();

    // 入力
    input! {
        n: usize, // 文字列の長さ
        s: Chars, // 入力文字列
    }

    // 文字列の長さが3文字未満の場合はNoを出力
    if n < cmp_sz {
        println!("No");
        return;
    }

    // 末尾3文字を取り出す
    let back_s = s[n - cmp_sz..].to_vec();
    
    // 末尾3文字が"tea"と一致するかどうかを判定
    println!("{}", if back_s == cmp_str { "Yes" } else { "No" });
}

 ABC418-B問題
https://atcoder.jp/contests/abc418/tasks/abc418_b
文字列 S の部分文字列について、充填率の最大値を求める問題です。充填率は以下の式で定義されます。

\text{充填率} = \frac{x - 2}{|t| - 2}
ここで、x は部分文字列内の文字 t の個数、|t| は部分文字列の長さです。
解説
部分文字列の開始位置 from と終了位置 to を全探索します。以下の条件を満たす部分文字列について、充填率を計算してその最大値を求めます。
部分文字列の開始位置と終了位置にある文字がどちらも t である。
部分文字列の長さが3以上である。
コード
abc418b.rs
use proconio::{input, marker::Chars};

fn main() {
    // 入力
    input! {
        s: Chars, // 文字列
    }

    let mut ans = 0.0;

    // 開始位置と終了位置([from..to])を全探索
    for from in 0..s.len() {
        for to in 0..s.len() {
            // 以下を全て満たす場合に、充填率をチェックする
            // 1. 選択した位置がfrom < toである
            // 2. fromとtoにある文字がどちらもtである
            // 3. 取り出した長さが3以上である
            if from >= to { continue; }
            if s[from] != 't' || s[to] != 't' { continue; }
            let len = to + 1 - from;
            if len < 3 { continue; }

            // tの個数を数える
            let mut cnt = 0;
            for i in from..=to {
                if s[i] == 't' { 
                    cnt += 1;
                }
            }

            // 充填率を計算して、最大値を更新
            let fill_rate = (cnt - 2) as f64 / (len - 2) as f64;
            ans = ans.max(fill_rate);
        }
    }

    // 充填率の最大値を出力
    println!("{}", ans);
}

 ABC418-C問題
https://atcoder.jp/contests/abc418/tasks/abc418_c
次のルールのゲームで、プレイヤーが勝つために必要な最小のティーバッグの個数を求める問題です。
プレイヤーが整数 x を選択する。
ディーラーは、ラベル(フレーバー番号)が付いたティーバッグを合計 x 個プレイヤーに渡す。
プレイヤーはその中から、合計 B 個選択する。
プレイヤーが選択した B 個が全て同じラベルならプレイヤーの勝ち、そうでなければプレイヤーの負け。
解説
まずディーラーの戦略ですが、プレイヤーが勝つ条件（同じフレーバーのティーバッグを B 個選ぶ）を阻止するため、各フレーバーから最大でも B-1 個までしか渡さない戦略を取ります。逆に、各フレーバーから B-1 個ずつ取った合計が x 個に満たなかった場合はディーラーが負けるので、その個数を求めればよいです。
ただし、各クエリでフレーバーから取り出す個数を1つずつ計算すると、クエリ1回あたりの計算量は O(N) 、全体での計算量は O(QN) となります。そのままでは実行時間制限以内に解くことができないため、各フレーバーから取り出す個数について、以下の2つに分けて高速に計算します。
B-1 個未満しかないフレーバーについて

各フレーバーからティーバッグを全て取り出します。

これは、事前に累積和を計算しておき、「 B-1 個未満のフレーバーの総和」の個数 を求めます。
B 個以上あるフレーバーについて

各フレーバーから B-1 個ずつティーバッグを取りだして、1つだけ1個多く取ります。

したがって、必要な個数は「 (B-1) \times \text{フレーバー数} + 1 」個になります。
1と2の境界を特定して、1と2の値の合計を求めることで、必要個数 x が求められます。1.と2.の境界は二分探索を用いることで、クエリ1回あたりの計算量は O(\log{N}) 、全体での計算量は O(Q \log{N}) に改善されるため、本問題を解くことができます。

なお、B がどのフレーバーにあるティーバッグの個数よりも大きい場合、プレイヤーが勝つ方法はないため、-1 を出力します。
コード
abc418c.rs
use proconio::input;
const INF: usize = 1 << 60;

fn main() {
    // 入力
    input! {
        n: usize, // フレーバーの数
        q: usize, // クエリ数
        mut a: [usize; n], // 各フレーバーにあるティーバッグの数
    }
    
    // フレーバーのティーバッグ数を昇順にソート
    a.sort();
    
    // 最大値を取得
    let amax = *a.iter().max().unwrap();
    
    // 累積和を計算
    let mut acc_a = vec![0; n+1];
    for i in 0..n {
        acc_a[i+1] = acc_a[i] + a[i];
    }

    // 配列のインデックスを1始まりにするため、ダミーの0を追加
    a.insert(0, 0);

    // 各クエリに対して処理
    for _ in 0..q {
        input! {
            b: usize, // 選択するティーバッグ数
        }
        solve(amax, &a, &acc_a, n, b);
    }
}

fn solve(
    amax: usize,
    a: &Vec<usize>,
    acc_a: &Vec<usize>,
    n: usize,
    b: usize
) {
    // b が最大値より大きい場合は不可能
    if amax < b {
        println!("-1");
        return;
    }

    // b-1 未満のフレーバーの個数を取得
    let pos = below_bound(a, b-1);

    // 必要なティーバッグ数を計算
    // - $b-1$ 未満のフレーバーからは全て取り出す
    // - $b-1$ 以上のフレーバーからは、各フレーバーから b-1 個ずつ + 1個取り出す
    let ans = acc_a[pos] + (n - pos) * (b-1) + 1;
    println!("{}", ans);
}

// 二分探索
// x以下の最大のposを返す。0番目より小さい値では異常値として、「1<<60」を返す
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}
}

 ABC418-D問題
https://atcoder.jp/contests/abc418/tasks/abc418_d
01文字列 T の部分文字列について、NXOR(排他的論理和の否定)の結果が1となる個数の総和を求める問題です。
解説
部分文字列に対してNXORを計算する際、どの順番で計算しても結果は同じになります。そのため、文字を1つずつ選びながらNXORを計算すればよいです。NXORの結果は0または1の2つの状態しかないため、動的計画法（DP）を用いて、特定の文字を追加したときに作れる状態（0または1）の個数を数えていきます。

DPの状態、遷移は以下のように定義します。
状態

dp[\text{cur}][\text{state}]：文字列のcur文字目まで見たとき、NXORの結果がstate（0または1）になる部分文字列の個数。
遷移

次に追加する文字( 0 , 1 )と、直前の状態(なし, 0 , 1 )の組み合わせで、次の状態が決まります。次の状態への遷移は以下の通りになります。


次に追加する文字
現在の状態
次の状態


0
なし
0

0
0
1

0
1
0

1
なし
1

1
0
0

1
1
1

最後に、各終了位置でNXORの結果が1となる部分文字列の個数を合計します。
コード
abc418d.rs
use proconio::{input, marker::Chars};

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

    // dp[cur文字目まで見た][処理後の状態(0,1)]=cur文字目を追加した時に作れる個数
    let mut dp = vec![vec![0usize; 2]; n + 1];

    // 開始の状態を全探索
    for cur in 0..n {
        if t[cur] == '0' {
            // 初めて文字を選択
            dp[cur + 1][0] += 1;
            // 現在の状態が0の場合、NXORの結果が1になる
            dp[cur + 1][1] += dp[cur][0];
            // 現在の状態が1の場合、NXORの結果が0になる
            dp[cur + 1][0] += dp[cur][1];
        } else {
            // 初めて文字を選択
            dp[cur + 1][1] += 1;
            // 現在の状態が0の場合、NXORの結果が0になる
            dp[cur + 1][0] += dp[cur][0];
            // 現在の状態が1の場合、NXORの結果が1になる
            dp[cur + 1][1] += dp[cur][1];
        }
    }

    // 各終了位置でNXORの結果が1になる個数の合計値を求める
    let mut ans = 0;
    for i in 1..=n {
        ans += dp[i][1];
    }
    println!("{}", ans);
}

 ABC418-E問題
https://atcoder.jp/contests/abc418/tasks/abc418_e
与えられた点から、任意の4点を選んで作ることができる台形の個数を求める問題です。
解説
台形を作るためには2組の平行な線分が必要ですが、平行四辺形を作った場合は台形が2回数えられてしまいます。

したがって、まず台形の候補を数え、その中から平行四辺形の個数を引く必要があります。

具体的には、以下1~3の手順で求めることができます。
台形の個数を数える

2点を選んで線分を作り、その線分の傾きを記録します。同じ傾きを持つ線分の中から2つを選ぶことで台形を作ることができます。
平行四辺形の個数を数える

2点を選んで線分を作り、その線分の中点の座標を記録します。同じ中点の座標を持つ線分の中から2つを選ぶことで平行四辺形を作ることができます。
重複を除いた台形の個数

台形の個数 - 平行四辺形の個数 により、求める台形の個数になります。
コード
abc418e.rs
use std::collections::HashMap;
use num::integer::gcd;
use proconio::input;

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

    // 線分の傾き(dy, dx)、中点座標をmapで管理
    let mut mp_slope = HashMap::new();
    let mut mp_midpoint = HashMap::new();

    // 2点を選んで線分を作る
    for i in 0..n {
        for j in i+1..n {
            // 線分の傾きを求める
            let slope = calc_slope(xy[i], xy[j]);
            // 中点の座標を求める(2で割るのは省略し、2倍値で管理)
            let midpoint = calc_midpoint(xy[i], xy[j]);
            // 傾きと中点をmapに格納
            *mp_slope.entry(slope).or_insert(0) += 1;
            *mp_midpoint.entry(midpoint).or_insert(0) += 1;
        }
    }

    let mut ans = 0;

    // 同じ傾きの線分から台形を作る個数を加算
    for (_key, value) in mp_slope {
        ans += value * (value - 1) / 2;
    }
    // 同じ中点の線分から平行四辺形を作る個数を減算
    for (_key, value) in mp_midpoint {
        ans -= value * (value - 1) / 2;
    }

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

// 線分の傾きを計算する関数
fn calc_slope(a: (i64, i64), b: (i64, i64)) -> (i64, i64) {
    let mut dy = a.1 - b.1;
    let mut dx = a.0 - b.0;
    // 分子が0の場合
    if dy == 0 {
        dx = 1;
    }
    // 分母が0の場合
    else if dx == 0 {
        dy = 0;
    }
    // 上記以外
    else {
        // 分母が正になるようにする
        if dx < 0 {
            dy *= -1;
            dx *= -1;
        }
        // dy, dxを最大公約数で割る
        let gcd = gcd(dy.abs(), dx.abs());
        dy /= gcd;
        dx /= gcd;
    }
    (dy, dx)
}

// 線分の中点を計算する関数
fn calc_midpoint(a: (i64, i64), b: (i64, i64)) -> (i64, i64) {
    let my = a.1 + b.1;
    let mx = a.0 + b.0;
    (my, mx)
}
次に追加する文字	現在の状態	次の状態
`0`	なし	`0`
`0`	`0`	`1`
`0`	`1`	`0`
`1`	なし	`1`
`1`	`0`	`0`
`1`	`1`	`1`
ABC418-A

ABC418-B

ABC418-C

ABC418-D

ABC418-E

Discussion
