👨‍🍳

ABC391:Rustで解く!問題解説

2025/02/02に公開

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

A問題

  • 問題

https://atcoder.jp/contests/abc391/tasks/abc391_a

  • 解説

NS に、 SN に、 EW に、 WE に変換します。

  • コード
use proconio::{input, marker::Chars};

fn main() {
    input! {
        d: Chars
    }
    let from_list = ['N', 'S', 'E', 'W']; // 変換元のリスト
    let to_list = ['S', 'N', 'W', 'E'];   // 変換先のリスト

    // 各文字に対して変換を行い、結果を出力する
    for &dd in &d {
        print!("{}", get_convert_char(dd, &from_list, &to_list));
    }
    println!();
}

fn get_convert_char(now_c: char, from_list: &[char], to_list: &[char]) -> char {
    // 変換元リストから現在の文字を検索し、対応する変換先の文字を返す
    for i in 0..from_list.len() {
        if from_list[i] == now_c {
            return to_list[i];
        }
    }
    // 変換元リストに存在しない場合のデフォルト文字
    return '.';
}

B問題

  • 問題

https://atcoder.jp/contests/abc391/tasks/abc391_b

  • 解説

グリッド S について、①「グリッド T の開始位置(左上)のマス」を全探索します。①を決めた上で、グリッド T 上のマスとすべて一致する位置を見つけます。

  • コード
use proconio::{input, marker::Chars};

fn main() {
    input!{
        n: usize, m: usize,
        s: [Chars; n],
        t: [Chars; m],
    }

    // 探索するサイズ
    let ck_sz = n - m + 1;

    // 開始位置の全探索
    for si in 0..ck_sz {
        for sj in 0..ck_sz {
            if is_all_collect(si, sj, &s, &t, m) {
                println!("{} {}", si + 1, sj + 1);
                return;
            }
        }
    }
    println!("-1 -1");
}

fn is_all_collect(si: usize, sj: usize, gd_s: &Vec<Vec<char>>, gd_t: &Vec<Vec<char>>, t_sz: usize) -> bool {
    for i in 0..t_sz {
        for j in 0..t_sz {
            if gd_s[si + i][sj + j] != gd_t[i][j] { return false; }
        }
    }
    true
}

C問題

  • 問題

https://atcoder.jp/contests/abc391/tasks/abc391_c

  • 解説

シミュレーションを用いて解くことができます。ただし、各クエリで計算量が O(N) になるような実装をしてしまうと、計算量の全体が O(NQ) となり、実行時間に収まりません。そのため、各クエリを効率的に処理する必要があります。

  • 1 P H: 鳩 P を巣 H に移動させる。

鳩が現在どの位置にいるのかを毎回探すと、1回あたりの計算量が O(N) になってしまいます。そこで、各鳩の現在位置を記録することにします。

  • 2 : 複数の鳩がいる巣の個数を出力する。

2匹以上の鳩がいる巣を探すと、1回あたりの計算量が O(N) になってしまいます。そこで、①「各巣にいる鳩の数」および②「2匹以上鳩がいる巣の数」を記録し、クエリ1での鳩の移動に合わせて都度更新します。②については、巣にいる鳩が1匹から2匹に増えたときに1つ増やし、2匹から1匹に減ったときに1つ減らせばよいです。

  • コード
use proconio::{input, marker::Usize1};

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

    // 鳩iが現在いる座標を初期化
    let mut now_hato = vec![0; n];
    for i in 0..n { now_hato[i] = i; }

    // 位置iにいる鳩の個数を初期化
    let mut su_hato = vec![1; n];

    // 一つの巣に2匹以上いる数の初期化
    let mut more_than_two = 0;

    for _ in 0..q {
        input! {
            nm: usize,
        }
        // 鳩を移動させる
        if nm == 1 {
            input! {
                // 移動させる鳩と移動後の位置
                p: Usize1, h: Usize1
            }
            let cpos = now_hato[p];
            
            // 鳩の情報を更新
            update_hato(p, cpos, h, &mut now_hato, &mut su_hato, &mut more_than_two);
        }
        // 一つの巣に2匹以上いる数を答える
        else {
            println!("{}", more_than_two);
        }
    }
}

fn update_hato(i: usize, cpos: usize, npos: usize, now_hato: &mut Vec<usize>, su_hato: &mut Vec<usize>, more_than_two: &mut usize) {
    // 移動前と移動後の個数を取得
    let from_cnt = su_hato[cpos];
    let to_cnt = su_hato[npos];
    
    // 増減を更新(2からの減少、1からの増加で増減)
    if from_cnt == 2 { *more_than_two -= 1; }
    if to_cnt == 1 { *more_than_two += 1; }

    // cposの個数-1, nposの個数+1
    su_hato[cpos] -= 1;
    su_hato[npos] += 1;

    // 鳩iがcposからnposへ移動
    now_hato[i] = npos;
}

D問題

  • 問題

https://atcoder.jp/contests/abc391/tasks/abc391_d

  • 解説

各ブロックについて高さが低い順に配置し、列毎に①「下から x 番目には、高さ h にブロック i がある」という情報を持たせます。その上で、以下の操作が出来なくなるまで繰り返します。

  • ①の情報をもとに最下段のブロックを横に見ていき、全ての列にブロックがあればそれらをまとめて消し、それらのブロックの時刻に②「ブロックを消す直前の時刻のmax」を記録する。

②の時刻は、「その段で見た中で最も高さがあるもの」と同義になります。
そのため、この時調べたブロックは②の時刻以内であれば存在するということになります。

  • コード
use proconio::{input, marker::Usize1};
use std::collections::VecDeque;
use std::cmp::max;
const INF: usize = 1 << 60;

fn main() {
    input! {
        n: usize, w: usize,
    }
    // (縦, 横, idx)でまとめて、縦で昇順に並べる
    let mut blocks = Vec::new();
    for i in 0..n {
        input! {
            // 入力は横、縦
            width: Usize1, height: Usize1,
        }
        blocks.push((height, width, i));
    }
    blocks.sort();

    // 各ブロックを列ごとに配置(最下段にする時刻(高さ), idx)
    let mut put_blocks = vec![VecDeque::new(); w];
    for (height, width, i) in blocks {
        put_blocks[width].push_back((height, i));
    }

    // ブロックが消える直前の時刻
    let mut exists_time = vec![INF; n];

    // 最下段から1段ずつ、各列のブロックを調べる
    loop {
        // 最下段の高さの最大の時刻を調べる
        let max_time = get_arrive_time(&put_blocks, w);
        if max_time == INF { break; }

        // 一列全てブロックがある場合、全て取り出して時刻を記録
        remove_blocks(&mut put_blocks, &mut exists_time, w, max_time);
    }

    // 各クエリについて答える
    input! {
        q: usize,
    }
    for _ in 0..q {
        input! {
            // 時刻、ブロック番号
            t: usize, a: Usize1,
        }
        println!("{}", if exists_time[a] >= t { "Yes" } else { "No" });
    }
}

fn get_arrive_time(put_blocks: &Vec<VecDeque<(usize, usize)>>, w: usize) -> usize {
    let mut ret = 0;
    for i in 0..w {
        // ブロックが取り出せない場合
        if put_blocks[i].is_empty() { return INF; }

        let block = *put_blocks[i].front().unwrap();
        ret = max(ret, block.0);
    }
    ret
}

fn remove_blocks(put_blocks: &mut Vec<VecDeque<(usize, usize)>>, exists_time: &mut Vec<usize>, w: usize, time: usize) {
    for i in 0..w {
        let block = put_blocks[i].pop_front().unwrap();
        exists_time[block.1] = time;
    }
}

E問題

  • 問題

https://atcoder.jp/contests/abc391/tasks/abc391_e

  • 解説

01 文字列の各文字を葉として扱い、根を調べていきます。
アルゴリズムとしては動的計画法(DP)を用いて、以下を求めることで問題を解決できます。

  • i を0または1にするための操作手数の最小値

一番下の葉から順に、「3つの子の葉の組み合わせ (0,0,0) から (1,1,1) までの8通り」を考え、「直属の親の葉を0または1」に設定していきます。
親の葉を0または1にするための3つの子の葉の組み合わせは以下であり、各組み合わせの中から操作手数の合計が最も少なくなるものを選択します。

  • 親の葉を0にする場合 → (0,0,0), (0,0,1), (0,1,0), (1,0,0) のいずれか
  • 親の葉を1にする場合 → (1,1,1), (1,1,0), (1,0,1), (0,1,1) のいずれか

なお、最終的な答えについてですが、最初の文字列から 01 が多いものをそのまま選んだ結果は必ず0手になるため、これと反対の操作を選択したものが答えとなります。

  • コード
use proconio::{input, marker::Chars};
use std::cmp::min;
use std::mem::swap;
const INF : usize = 1 << 60;

fn main() {
    input!{
        n: usize,
        s: Chars,
    }
    let mut child_sz = s.len();

    // 子(0または1) dp[葉i] = (0または1)にするための操作手数を初期化
    let mut child0_dp = vec![0; child_sz];
    let mut child1_dp = vec![0; child_sz];
    for i in 0..child_sz {
        if s[i] == '0' {
            // '0' の場合、親を '1' にするための手数は1
            child1_dp[i] = 1;
        } else if s[i] == '1' {
            // '1' の場合、親を '0' にするための手数は1
            child0_dp[i] = 1;
        }
    }

    // 子 -> 親に遷移する際の操作手数の最小を調べる
    for _ in 0..n {
        // 親 dp の操作手数を初期化
        let mut parent_sz = child_sz / 3;
        let mut parent0_dp = vec![INF; parent_sz];
        let mut parent1_dp = vec![INF; parent_sz];

        // 親を1つずつ調べる
        for j in 0..parent_sz {
            let a = (child0_dp[3*j  ], child1_dp[3*j  ]);
            let b = (child0_dp[3*j+1], child1_dp[3*j+1]);
            let c = (child0_dp[3*j+2], child1_dp[3*j+2]);
            // 親を0または1に選択した時の操作手数の最小を取得
            parent0_dp[j] = calc_min_cost0(a, b, c);
            parent1_dp[j] = calc_min_cost1(a, b, c);
        }

        swap(&mut child0_dp, &mut parent0_dp);
        swap(&mut child1_dp, &mut parent1_dp);
        swap(&mut child_sz, &mut parent_sz);
    }
    // 操作手数が0でない方が答え
    println!("{}", if child0_dp[0] != 0 {child0_dp[0]} else {child1_dp[0]});
}

fn calc_min_cost0(a: (usize, usize), b: (usize, usize), c: (usize, usize)) -> usize {
    // (0,0,0),(0,0,1),(0,1,0),(1,0,0)のいずれかを選択する際の最小手数を計算
    let mut ret = INF;
    ret = min(ret, a.0 + b.0 + c.0);
    ret = min(ret, a.0 + b.0 + c.1);
    ret = min(ret, a.0 + b.1 + c.0);
    ret = min(ret, a.1 + b.0 + c.0);
    ret
}

fn calc_min_cost1(a: (usize, usize), b: (usize, usize), c: (usize, usize)) -> usize {
    // (1,1,1),(1,1,0),(1,0,1),(0,1,1)のいずれかを選択する際の最小手数を計算
    let mut ret = INF;
    ret = min(ret, a.1 + b.1 + c.1);
    ret = min(ret, a.1 + b.1 + c.0);
    ret = min(ret, a.1 + b.0 + c.1);
    ret = min(ret, a.0 + b.1 + c.1);
    ret
}

Discussion