ABC381:Rustで解く！問題解説

AtCoder Beginner Contest 381のA~E問題をRustで解いた際の解法をまとめました。

A問題

• 問題

https://atcoder.jp/contests/abc381/tasks/abc381_a

• 解説

文字列の長さを$N = 2x + 1$とし、文字列内で1が$x$個、/が1個、2が$x$個になるかを判定します。
もしこれらの条件を満たさない場合はNoと出力し、条件を満たす場合はYesと出力します。

• コード

use proconio::{input, marker::Chars};

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

    // nが奇数でない場合は"NO"を出力
    if n % 2 != 1 { 
        println!("No");
        return;
    }

    let ck_1 = n / 2; // x の値、前半と後半の1の個数および2の個数を決定

    // 前半がすべて '1' であることを確認
    for i in 0..ck_1 {
        if s[i] != '1' {
            println!("No");
            return;
        }
    }

    // 中央の文字が '/' であることを確認
    if s[ck_1] != '/' {
        println!("No");
        return;
    }

    // 後半がすべて '2' であることを確認
    for i in ck_1+1..n {
        if s[i] != '2' {
            println!("No");
            return;
        }
    }

    // すべての条件を満たしている場合は"Yes"
    println!("Yes");
}

B問題

• 問題

https://atcoder.jp/contests/abc381/tasks/abc381_b

• 解説

与えられた文字列を隣接する2つの文字を順番に見ていきます。
各ペアの文字が同じであることを確認し、さらにその文字が過去に現れたことがない場合にのみ次を見ます。
つまり、各ペアは同じ文字であり、その文字が他のペアに再度登場しないことを確認します。
この条件を満たす場合はYesを、それ以外の場合はNoを出力します。

• コード

use proconio::{input, marker::Chars};

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

    let sz = s.len();  // 文字列の長さ

    // 文字列の長さが偶数でない場合は"NO"を出力
    if sz % 2 != 0 {
        println!("No");
        return;
    }

    // 使用済みの英小文字を管理するためのベクター
    let mut used = vec![false; 26];

    // 隣接する2つの文字が同じで、まだ使われていない文字であることを確認
    for i in 0..sz/2 {
        if s[2*i] != s[2*i + 1] {  // 隣接する2文字が異なる場合は"NO"
            println!("No");
            return;
        }

        let moji_index = s[2*i] as usize - 0x61;  // 'a'のASCII値（0x61）を引いてインデックスを取得

        // すでにその文字が使われている場合は"NO"
        if used[moji_index] {
            println!("No");
            return;
        }

        // 使用した文字としてマーク
        used[moji_index] = true;
    }

    // すべての条件を満たした場合は"Yes"
    println!("Yes");
}

C問題

• 問題

https://atcoder.jp/contests/abc381/tasks/abc381_c

• 解説

まず、ランレングス圧縮を使って、連続する同じ文字をまとめます。
その後、圧縮された文字列を見て、1, /, 2の順番で構成されている部分を探します。
このとき、/が1個で、1と2がそれぞれ複数個連続している場合にその形を確認します。
1と2の個数の最小値を取り、それに基づいて構成できる文字列の長さを計算します。
具体的には、1の末端の個数と、2の先頭の個数を取り、/と合わせて最大の長さを求めます。

• コード

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

fn main() {
    input! {
        _n: usize,  // 文字列の長さ（使用していない）
        s: Chars,   // 文字列
    }

    // ランレングス圧縮を実行
    let rangs = ranglen(&s);

    let mut ans = 1;  // 最小の答えは1（最初の値として設定）

    // ランレングス圧縮後、3つのペアが存在しない場合はそのまま出力
    if rangs.len() < 3 {
        println!("{}", ans);
        return;
    }
    
    // 3つのペアを順番に見ていく
    for i in 0..rangs.len()-2 {
        // 1 / 2の形を見つける
        // 1が複数個、/が1個、2が複数個で構成されていることを確認
        if rangs[i].0 == '1' && rangs[i+1].0 == '/' && rangs[i+2].0 == '2' && rangs[i+1].1 == 1 {
            // 1の個数と2の個数の最小値を取り、その2倍 + 1を計算
            let sz = min(rangs[i].1, rangs[i+2].1) * 2 + 1;
            // 現在の最大長さと比較して、最大値を更新
            ans = max(ans, sz);
        }
    }

    // 最大の長さを出力
    println!("{}", ans);
}

// ランレングス圧縮関数
// 連続する同じ文字をまとめて、文字とその出現回数のタプルを返す
pub fn ranglen(arr: &Vec<char>) -> Vec<(char, usize)> {
    let len = arr.len();
    let mut arr_ret = Vec::new();
    let mut tail = 0;
    let mut top = 0;
    while tail < len {
        let now_c = arr[tail];
        // 同じ文字が続く限りtopを進める
        while top < len && now_c == arr[top] {
            top += 1;
        }
        // 現在の文字とその出現回数を追加
        arr_ret.push((now_c, top - tail));
        tail = top;  // 次のグループに移動
    }
    arr_ret
}

D問題

• 問題

https://atcoder.jp/contests/abc381/tasks/abc381_d

• 解説

尺取り法を使って、連続した2個セットの要素を追加していき、追加した要素の種類をHashSetで管理します。
要素を取り出す場合も、同じく2個セットで取り出します。
最初の位置を1つ目から始める場合と、2つ目から始める場合の2パターンを試し、
どちらのパターンでより長い連続した2個セットを作れるかを計算します。

• コード

use proconio::input;
use std::collections::HashSet;
use std::cmp::max;

fn main() {
    input! {
        n: usize,  // 配列の長さ
        a: [usize; n],  // 配列
    }

    let mut ans = 0;  // 最長の連続部分列の長さ

    // 尺取り法
    // 1つ目から開始した場合、2つ目から開始した場合の2パターンを試す
    for spos in 0..2 {
        let mut tail = spos;  // 先頭のインデックス
        let mut top = spos;   // 末尾のインデックス
        let mut st = HashSet::new();  // 追加された要素を管理するHashSet

        // 尺取り法で連続した2個セットを追加・取り出す
        while tail < n-1 {
            // 追加できるだけ追加（同じ要素が続いていて、HashSetに含まれていない場合）
            while top < n-1 && a[top] == a[top+1] && !st.contains(&a[top]) {
                st.insert(a[top]);  // 追加した要素をHashSetに記録
                top += 2;  // 2個セットで進める
            }

            // 現在の範囲が有効な場合、最長長さを更新
            if top >= tail {
                ans = max(ans, top - tail);
            }

            // 要素を取り出す
            if top == tail {
                // topとtailが同じ位置にいる場合、2つ目の要素を進める
                top += 2;
                tail += 2;
            } else {
                // tailの要素を取り出して進める
                st.remove(&a[tail]);
                tail += 2;
            }
        }
    }

    // 結果の最長長さを出力
    println!("{}", ans);
}

E問題

• 問題

https://atcoder.jp/contests/abc381/tasks/abc381_e

• 解説

まず、文字列内の1と2の個数の累積和と、/の位置を記録します。
次に、各クエリに対して/の位置を二分探索を使って探します。
/の位置を固定し、その左右にある1と2の個数を数え、最小値を求めます。
この最小値が最も大きくなる位置を探し、最適解を求めます。
二分探索の過程では、1の個数が2の個数よりも多ければ/の位置を左側にずらし、逆に1の個数が少なければ右側にずらします。
これにより、効率的に最適な位置を見つけます。

• コード

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

fn main() {
    input! {
        n: usize, q: usize,  // 文字列の長さnとクエリ数q
        s: Chars,  // 文字列
    }

    // 1, 2の個数の累積和と/の位置を記録
    let mut one = vec![0; n+1];  // 1の累積和
    let mut two = vec![0; n+1];  // 2の累積和
    let mut pos_sura = Vec::new();  // /の位置を保存

    // 累積和の計算と/の位置の記録
    for i in 0..n {
        if s[i] == '1' { one[i+1] = 1; }
        if s[i] == '2' { two[i+1] = 1; }
        if s[i] == '/' { pos_sura.push(i+1); }
    }

    // 累積和の計算
    for i in 0..n {
        one[i+1] += one[i];
        two[i+1] += two[i];
    }

    // クエリ処理
    for _ in 0..q {
        input! {
            l: usize, r: usize,  // クエリ範囲
        }

        let mut ans = 0;  // 最適解を格納

        // [l, r]の範囲内にある/の位置を二分探索
        let mut spos = lower_bound(&pos_sura, l);
        let mut epos = lower_bound(&pos_sura, r+1);

        // /がない場合
        if spos == epos {
            println!("0");
            continue;
        }

        // 二分探索で最適解を探す
        for _ in 0..30 {
            let mpos = (spos + epos) / 2;  // 中央の/の位置
            let i = pos_sura[mpos];  // /の位置のindex
            let one_cnt = one[i-1] - one[l-1];  // lからi-1までの1の個数
            let two_cnt = two[r] - two[i];  // iからrまでの2の個数
            ans = max(ans, min(one_cnt, two_cnt) * 2 + 1);  // 1と2の個数の最小値を元に最適解を更新

            // 次に調べる位置を決める
            if one_cnt > two_cnt {
                epos = mpos;  // 1の個数が多ければ/を左側にずらす
            } else {
                spos = mpos;  // 2の個数が多ければ/を右側にずらす
            }
        }

        println!("{}", ans);  // 最適解を出力
    }
}

// 二分探索
// x以上の最小の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
}