Zenn
👨‍🍳

ABC393:Rustで解く！問題解説

2025/02/16に公開
Rust
競技プログラミング
AtCoder
tech

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

A問題

問題

https://atcoder.jp/contests/abc393/tasks/abc393_a

解説

入力で与えられるS_1とS_2は、以下の4通りに場合分けして処理することができます。

  • S_1とS_2が sick の場合
  • S_1が sick、S_2が fine の場合
  • S_1が fine、S_2が sick の場合
  • S_1とS_2が fine の場合

各場合に応じた出力を行います。

コード

use proconio::input;

fn main() {
    input! {
        s1: String,
        s2: String
    }
    if s1 == "sick" && s2 == "sick" {
        println!("1");
    } else if s1 == "sick" && s2 == "fine" {
        println!("2");
    } else if s1 == "fine" && s2 == "sick" {
        println!("3");
    } else {
        println!("4");
    }
}

B問題

問題

https://atcoder.jp/contests/abc393/tasks/abc393_b

解説

等間隔で選んだ3つの文字がA, B, Cとなる組み合わせの総数を数えます。数え上げは以下1~3の手順で行います。

  1. Aの位置を決める。
  2. 1で決めた位置から、j文字ずつ飛ばし( j=1,2,... )で2つ選び、その2つがBとCである場合、適切な組み合わせとしてカウントします。
  3. 全てのAの位置に対して、2を行います。

コード

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

fn main() {
    input! {
        s: Chars,
    }
    let sz = s.len();

    let mut ans = 0;

    // 開始の'A'の位置を全探索
    for i in 0..sz {
        if s[i] != 'A' { continue; }
        
        // j個飛ばしで全探索
        for j in 0..sz {
            if i + 2 * j >= sz { break; }
            
            // 'A', 'B', 'C'になっている個数を数える
            if s[i + j] == 'B' && s[i + 2 * j] == 'C' { 
                ans += 1;
            }
        }
    }
    println!("{}", ans);
}

C問題

問題

https://atcoder.jp/contests/abc393/tasks/abc393_c

解説

頂点ごとの隣接リストを集合で管理しながら作成します。その際、以下のいずれかに該当する辺の本数を数えます。

  • 自己ループの辺
  • 一度見たことがある2頂点の組の辺

コード

use proconio::{input, marker::Usize1};
use std::collections::HashSet;

fn main() {
    input! {
        n: usize, m: usize,
    }

    // 追加しなかった辺の本数
    let mut ans = 0;

    // 無向グラフの隣接リストを作る。(同じ組の辺や、自己ループの辺は除く)
    let mut uv = vec![HashSet::new(); n];
    for _ in 0..m {
        input! {
            u: Usize1, v: Usize1,
        }
        // 同じ組の辺や、自己ループの辺の場合は、その本数を数える
        if is_myself_loop(u, v) || is_contained_edge(u, v, &uv) {
            ans += 1;
        }
        // 隣接リストに辺を追加
        else {
            add_edge(u, v, &mut uv);
        }
    }

    println!("{}", ans);
}

// 自己ループの辺かどうかをチェック
fn is_myself_loop(u: usize, v: usize) -> bool {
    u == v
}

// 既にある組の辺かどうかをチェック
fn is_contained_edge(u: usize, v: usize, uv: &Vec<HashSet<usize>>) -> bool {
    if uv[u].contains(&v) { return true; }
    if uv[v].contains(&u) { return true; }
    false
}

// 辺の追加
fn add_edge(u: usize, v: usize, uv: &mut Vec<HashSet<usize>>) {
    uv[u].insert(v);
    uv[v].insert(u);
}

D問題

問題

https://atcoder.jp/contests/abc393/tasks/abc393_d

解説

1の固まりをどこに持ってくるのが最適なのかを考えます。文字列 S に含まれる1の並び順は変える必要がないため、1の固まりにした文字列 S' においても同じ並びでマッチングさせることができます。これを前提として、入力例1について、1の固まりを実際に配置した際の操作回数を考えます。

  1. 1の固まりを左端に配置した場合：左側にずらす操作は左から順に1 + 2 + 4で計7回。
  2. 1の固まりを左端から2番目に配置した場合：左側にずらす操作は左から順に0 + 1 + 3で計4回。
  3. 1の固まりを左端から3番目に配置した場合：左側にずらす操作は左から順に0 + 2、右側にずらす操作は1で計3回。
  4. 1の固まりを左端から4番目に配置した場合：左側にずらす操作は左から順に1、右側にずらす操作は2 + 1で計4回となります。

ここで①～④について、1の固まりの配置により操作回数がどのように変化するかに注目します。

  • ①→②に移した際は左側にずらす操作が3回減少 → 計3回減少。
  • ②→③に移した際は左側にずらす操作が2回減少し、右側にずらす操作が1回増加 → 計1回減少。
  • ③→④に移した際は左側にずらす操作が1回減少し、右側にずらす操作が2回増加 → 計1回増加。

このように調べていくと、1の固まりは両端に近いほど操作回数が増加し、中央に近いほど操作回数が減少することがわかります。
したがって、「元の文字列 S の1の中央」に「1の固まりの文字列 S' の1の中央」が来るような配置にするのが最適であり、そのときの操作回数を求めればよいです。

コード

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

fn main() {
    input!{
        n: usize,
        s: Chars,
    }

    // 1の出現位置を取得
    let pos_ones = get_pos_ones(n, &s);

    // 1の固まりの左端を取得
    let start_pos = get_left_pos(&pos_ones);
    
    // 「元の文字列の各1」と「1の固まりの各1」を左側からマッチングさせる
    // ずれている距離の絶対値を加算
    let mut ans = 0;
    for i in 0..pos_ones.len() {
        ans += (start_pos + i).abs_diff(pos_ones[i]);
    }
    println!("{}", ans);
}

// 1の出現位置を取得
fn get_pos_ones(n: usize, s: &Vec<char>) -> Vec<usize> {
    let mut vec = Vec::new();
    for i in 0..n {
        if s[i] == '1' {
            vec.push(i);
        }
    }
    vec
}

// 1の固まりの左端を取得
fn get_left_pos(ones: &Vec<usize>) -> usize {
    // 1の出現位置の中央値が、1の固まりの中央となるように合わせる
    // 1の個数が偶数の場合は中央値の左側とする。
    let middle = (ones.len() - 1) / 2;

    // 1の固まりの左端を取得
    // 1の固まりの中央値から、middle分だけずらす
    ones[middle] - middle
}

E問題

問題

https://atcoder.jp/contests/abc393/tasks/abc393_e

解説

本問題において最大公約数が X となるためには、 A_i と選んだ残り K-1 個の値が全て X で割り切れる必要があります。取りうる値の範囲は 1 から 10^6 となっているので、エラトステネスの篩を利用して以下を数え上げればよいです。

  1. 値 d を 1 倍、2 倍、... と見ていき、各 A_i と一致する個数を数えます。
    → この数え上げにより、各 A_i が d の倍数となる個数が分かります。

  2. 1の結果に基づき、K 個以上で割り切れる値 d について、1 倍、2 倍、... と見た値をマークします。
    → d を定数倍した値は、いずれも割り切れる個数が K 個以上なので、この時に見た d の最大値を記録します。

A_i の最大値を M とした場合、1、2の計算量はそれぞれ O(M\log{M}) であるため、実行時間制限以内に解くことができます。

コード

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

const MAX_VALUE: usize = 1_000_000;

fn main() {
    input! {
        n: usize, k: usize,
        a: [usize; n],
    }

    // 入力数列の各値の出現回数をカウント（1～MAX_VALUE）
    let cnt_array = build_cnt_array(&a);

    // 各候補約数 d (1～MAX_VALUE) について、入力数列中の d の倍数の個数を求める
    let divisor_array = erato_divisor_array(&cnt_array);

    // 各 x (1～MAX_VALUE) について、x を割り切る候補約数の中で、
    // 入力数列中に k 個以上の数が割り切れる約数のうち最大のものを求める
    let ans = erato_max_valid_divisor(&divisor_array, k);

    // 各入力値について、条件を満たす最大の約数を出力
    for &num in &a {
        println!("{}", ans[num]);
    }
}

// 入力された数列の各値の出現回数をカウントし、
// 1～MAX_VALUEの範囲で頻度配列を作成する
fn build_cnt_array(a: &[usize]) -> Vec<usize> {
    let mut ret = vec![0; MAX_VALUE + 1];
    for &num in a {
        ret[num] += 1;
    }
    ret
}

// 各候補約数 d (1～MAX_VALUE) について、
// 入力数列中の d の倍数の個数を求める  
fn erato_divisor_array(cnt_array: &[usize]) -> Vec<usize> {
    let mut ret = vec![0; MAX_VALUE + 1];

    for d in 1..=MAX_VALUE {
        let mut multi = d;
        let mut cnt = 0;
        while multi <= MAX_VALUE {
            cnt += cnt_array[multi];
            multi += d;
        }
        ret[d] = cnt;
    }
    ret
}

// 各 x (1～MAX_VALUE) について、x を割り切る候補約数のうち、
// 入力数列中に k 個以上の数が割り切れる約数の中で最大のものを求める  
// （x の約数で条件を満たす最大公約数を求める）
fn erato_max_valid_divisor(divisor_array: &[usize], k: usize) -> Vec<usize> {
    let mut ret = vec![0; MAX_VALUE + 1];

    // 各候補約数 d について、d が条件を満たすならば、その倍数全体に対して d を更新
    for d in 1..=MAX_VALUE {
        if divisor_array[d] < k { continue; }
        let mut multi = d;
        while multi <= MAX_VALUE {
            ret[multi] = max(ret[multi], d);
            multi += d;
        }
    }
    ret
}

F問題

問題

https://atcoder.jp/contests/abc393/tasks/abc393_f

解説

LIS（最長増加部分列）を求めるアルゴリズムを用いて問題を解きます。LISの計算には二分探索を用いる方法とセグメントツリーを使う方法がありますが、配列の要素制約が 10^9 と大きく、このサイズのメモリを確保できないため、前者の方法を選択します。

LISを求める際には、以下のDPテーブルを用意し、都度更新を行います。

DP[i] : 最長増加部分列のi個目の値の最小値

与えられるクエリについては、整数列を一度昇順に並び替えて i 個目の要素を追加した際に処理出来るクエリを全て処理し、DPテーブルの更新が終わった後にクエリの順に並べ直すことで対応します。

コード

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

fn main() {
    input! {
        n: usize, q: usize,
        a: [usize; n],
    }

    // クエリ（index, 値範囲, 入力順）をindexの昇順に並べる
    let mut query = Vec::new();
    for i in 0..q {
        input! {
            // r:index, x:値範囲
            r: Usize1, x: usize,
        }
        query.push((r, x, i));
    }
    query.sort();

    // LISのDP: dp[最長増加部分列i個] = i個目の値の最小値
    let mut dp = Vec::new();
    // 処理したクエリの個数
    let mut exe_cnt = 0;
    // ans: (入力順、値)
    let mut ans = Vec::new();
    
    for i in 0..n {
        // LISに要素を挿入
        insert_lis(&mut dp, a[i]);
        // 同じindexのクエリをすべて処理する
        while exe_cnt < q && query[exe_cnt].0 == i {
            // 値範囲以下の最長増加部分列の個数を取得
            let pos2 = below_bound(&dp, query[exe_cnt].1);
            if pos2 == INFS {
                ans.push((query[exe_cnt].2, 1));
            } else {
                ans.push((query[exe_cnt].2, pos2 + 1));
            }
            exe_cnt += 1;
        }
    }

    // クエリ順に並べ直して答える
    ans.sort();
    for i in 0..q {
        println!("{}", ans[i].1);
    }
}

// LISに要素を挿入
fn insert_lis(dp: &mut Vec<usize>, x: usize) {
    // x以上で最も小さい値を置き換え、置き換えが出来ないなら値を追加
    let pos = lower_bound(&dp, x);
    if pos == dp.len() {
        dp.push(x);
    } else {
        dp[pos] = x;
    }
}

// 二分探索
// x以上の最小のposを返す
pub fn lower_bound<T: std::cmp::PartialOrd>(dp: &Vec<T>, val: T) -> usize {
    let mut l = 0;
    let mut r = dp.len();
    while r - l > 0 {
        let m = (l + r) / 2;
        if dp[m] < val {
            l = m + 1;
        } else {
            r = m;
        }
    }
    l
}

const INFS: usize = 1 << 60;

// 二分探索
// x以下の最大のposを返す。0番目より小さい値では異常値として「1<<60」を返す
pub fn below_bound<T: std::cmp::PartialOrd>(dp: &Vec<T>, val: T) -> usize {
    let mut l = 0;
    let mut r = dp.len();
    while r - l > 0 {
        let m = (l + r) / 2;
        if dp[m] <= val {
            l = m + 1;
        } else {
            r = m;
        }
    }
    if l == 0 { INFS } else { l - 1 }
}

Discussion