ABC395:Rustで解く！問題解説

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

A問題

問題

https://atcoder.jp/contests/abc395/tasks/abc395_a

解説

数列 $A$ について、各隣接する2項について以下の条件を満たしているかどうかを順番に判定します。

$A_{i} < A_{i+1}$

どの2項でも条件を満たす場合は Yes、1箇所でも条件を満たさない箇所があれば、No となります。

コード

abc395a.rs

use proconio::input;
fn main() {
    // 入力
    input!{
        n: usize,
        a: [usize; n],
    }

    let mut f = true;
    for i in 0..n-1 {
        if a[i] >= a[i+1] {
            f = false;
            break;
        }
    }

    // 出力
    println!("{}", if f {"Yes"} else {"No"});
}

B問題

問題

https://atcoder.jp/contests/abc395/tasks/abc395_b

解説

各マスについて「端のマスへの最短距離」が偶数であれば # 、奇数であれば . を出力します。「端のマスへの最短距離」を求める手順は以下1~3の通りです。

1. 縦座標の「上部 $(0)$ への距離」と「下部 $(N-1)$ への距離」のうち、小さい方を選ぶ。
2. 横座標の「左部 $(0)$ への距離」と「右部 $(N-1)$ への距離」のうち、小さい方を選ぶ。
3. 1と2で得られた値の中で、小さい方を選ぶ。

コード

abc395b.rs

use proconio::input;
use itertools::Itertools;
use std::cmp::min;

fn main() {
    // 入力
    input! {
        n: usize,
    }

    let mut ans = vec![vec!['#'; n]; n];
    for i in 0..n {
        for j in 0..n {
            // 端への最短距離が奇数なら、'.'に設定
            if calc_side_dist(i, j, n) % 2 == 1 {
                ans[i][j] = '.';
            }
        }
    }
    
    // 出力
    for i in 0..n {
        println!("{}", ans[i].iter().join(""));
    }
}

fn calc_side_dist(row: usize, col: usize, n: usize) -> usize {
    let row_min = min(row, n - 1 - row);
    let col_min = min(col, n - 1 - col);
    
    // 縦と横の最短距離のうち、小さい方を返す
    min(row_min, col_min)
}

C問題

問題

https://atcoder.jp/contests/abc395/tasks/abc395_c

解説

尺取り法を用いて解くことができます。
数列 $A$ に現れる値を順番に集合に追加していき、既に持っている値が出てくるまで繰り返します。既に持っている値が見つかった場合は、「現在持っている値の個数 $+1$ 」が同じ値を複数個持つ状態となるため、その状態における値の最小値を更新します。その後は集合の中で最古の情報を1つ取り除いて、引き続き集合への要素の追加や最小値の更新を行います。これを可能な限り行っていきます。

コード

abc395c.rs

use proconio::input;
use std::collections::HashSet;
use std::cmp::min;
const INF: usize = 1 << 60;

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

    let mut ans = INF;
    
    // 尺取り法
    let mut st = HashSet::new();
    let mut tail = 0;
    let mut top = 0;
    while tail < n {
        // 既に持っている値が出てくるまで追加
        while top < n && !st.contains(&a[top]) {
            st.insert(a[top]);
            top += 1;
        }
        if top == n { break; }

        // 最小値を更新
        let val = st.len() + 1;
        ans = min(ans, val);
        
        // 先頭と末尾が同じなら、先頭を1つ進める
        if top == tail { top += 1; }
        // そうでないなら、末尾を1つ取り出す
        else { st.remove(&a[tail]); }
        // 末尾を1つ進める
        tail += 1;
    }

    // 出力
    if ans == INF {
        println!("-1");
        return;
    }
    println!("{}", ans);
}

D問題

問題

https://atcoder.jp/contests/abc395/tasks/abc395_d

解説

3種類のクエリに従い、鳩の移動と巣にいる鳩の位置を答えます。ただし、クエリ2で2つの巣の鳩を総入れ替えする処理をそのまま実装するとクエリ1つ当たりの計算量が $O(N)$ となります。そうすると、最悪ケースでの計算量が $O(NQ)$ となるため、実行時間制限内に解くことができません。これは、1つの巣に対して鳩が複数という一対多の関係にあるためで、一対一の関係で入れ替えられるような工夫が必要になります。
具体的な方法としては、各巣に対して箱を割り当てておきます。鳩は箱の中に入れるようにして、巣の入れ替えを行う際は箱ごと入れ替えを行うようにします。また、箱から巣の位置を特定するための情報も保持し、箱が入れ替わるタイミングで箱から見た巣の位置も変更します。
これらをまとめると、クエリ1〜3の操作は以下のように読み替えることができます。

1. 巣の中にある箱に鳩を入れる。
2. 2つの巣の箱を入れ替える。また、箱から見える巣の情報も入れ替える。
3. 鳩が入っている箱から見える巣を答える。

以上により、クエリ1〜3の各計算量が $O(1)$ 、クエリ全体でも計算量は $O(Q)$ になるため、実行時間制限内に解くことが可能になります。

コード

abc395d.rs

use proconio::input;

fn main() {
    // 出力
	input! {
        mut n: usize, q: usize,
    }
    // 実データを1始まりにするため、+1する
    n += 1;

    // 鳩iが入っている箱
    let mut in_box = vec![0; n];
    for i in 0..n { in_box[i] = i; }
    // 巣iが持っている箱
    let mut has_box = vec![0; n];
    for i in 0..n { has_box[i] = i; }
    // 箱iから見える巣
    let mut seen_su = vec![0; n];
    for i in 0..n { seen_su[i] = i; }

    // クエリ処理
    for _ in 0..q {
        input! {
            nm: usize,
        }

        if nm == 1 {
            input! {
                // 鳩と移動先の巣
                idx: usize, to: usize,
            }
            // 巣toが持っている箱の位置に、鳩を入れる
            let pos = has_box[to];
            in_box[idx] = pos;
        } else if nm == 3 {
            input! {
                // 鳩
                idx: usize,
            }
            // 鳩idxが入っている箱から見える巣を答える
            let pos = in_box[idx];
            println!("{}", seen_su[pos]);
        } else {
            input! {
                // 入れ替える巣
                pos1: usize, pos2: usize,
            }
            // 箱を交換
            has_box.swap(pos1, pos2);

            // 箱から見える巣を入れ替え先のものに更新
            let item1 = has_box[pos1];
            let item2 = has_box[pos2];
            seen_su[item1] = pos1;
            seen_su[item2] = pos2;
        }
    }
}

E問題

問題

https://atcoder.jp/contests/abc395/tasks/abc395_e

解説

ダイクストラ法のアルゴリズムを使用して問題を解決することができます。
入力のグラフの有向辺について、入力と同じ向きの辺を「表の辺」、逆向きの辺を「裏の辺」と呼ぶことにします。また同様に、辺の向きによって各頂点に2つの状態(表と裏)があると考えます。この有向辺および状態のグラフについて、頂点 $1$ から頂点 $N$ に移動する際の最短距離を求めます。
移動する際は、「現在の頂点の状態（表裏）」と「移動する辺（表裏）」を考慮して、「移動距離」と「移動後の頂点の状態（表裏）」を決定します。

1. 現在の頂点の状態が表、移動する辺が表の場合
   → 移動距離は $1$、移動後の頂点の状態は表

2. 現在の頂点の状態が表、移動する辺が裏の場合
   → 移動距離は $x+1$ 、移動後の頂点の状態は裏

3. 現在の頂点の状態が裏、移動する辺が表の場合
   → 移動距離は $x+1$ 、移動後の頂点の状態は表

4. 現在の頂点の状態が裏、移動する辺が裏の場合
   → 移動距離は $1$ 、移動後の頂点の状態は裏

頂点 $N$ の最短距離は、状態の表または裏の最短距離のうち、小さい方を出力します。

コード

abc395e.rs

use proconio::{input, marker::Usize1};
use std::collections::BinaryHeap;
use std::cmp::{min, Reverse};

const INF: i64 = 1 << 60;

fn main() {
    // 入力
    input!{
        n: usize, m: usize, x: i64,
        uv: [(Usize1, Usize1); m],
    }

    // グラフの辺を貼る。(有向辺を表、有向辺の逆辺を裏とする)
    let mut edge = vec![Vec::new(); n];
    for &(u, v) in &uv {
        // 辺の行先と表(true)裏(false)
        edge[u].push((v, true));
        edge[v].push((u, false));
    }

    // グラフの最短距離(表面、裏面)
    let mut dist1 = vec![INF; n];
    let mut dist2 = vec![INF; n];
    dist1[0] = 0;
    dist2[0] = x;

    // (現在距離、現在の位置、状態の表裏)として、キューを初期化
    let mut hp = BinaryHeap::new();
    hp.push(Reverse((dist1[0], 0, true)));
    hp.push(Reverse((dist2[0], 0, false)));
    
    // ダイクストラ法で、グラフの頂点への最短距離を調べる
    while let Some(item) = hp.pop() {
        let (cdist, cpos, cstate) = item.0;
        
        // 現在距離より最適な状態を既に見ている場合はスキップ
        if cstate && dist1[cpos] < cdist { continue; }
        if !cstate && dist2[cpos] < cdist { continue; }
        
        // 頂点の移動
        for &npos in &edge[cpos] {
            // 移動距離を決定(遷移先の表裏が異なる場合は、+x)
            let mut next_dist = cdist + 1;
            if cstate != npos.1 { next_dist += x; }
            
            // 表に遷移
            if npos.1 {
                update_dist_and_heap(next_dist, npos.0, npos.1, &mut dist1, &mut hp);
            }
            // 裏に遷移
            else {
                update_dist_and_heap(next_dist, npos.0, npos.1, &mut dist2, &mut hp);
            }
        }
    }

    // 結果を出力
    let ans = min(dist1[n-1], dist2[n-1]);
    println!("{}", ans);
}

fn update_dist_and_heap(next_dist: i64, npos: usize, next_state: bool, 
    dist: &mut Vec<i64>, hp: &mut BinaryHeap<Reverse<(i64, usize, bool)>>) {
    if next_dist >= dist[npos] { return; }
    dist[npos] = next_dist;
    hp.push(Reverse((next_dist, npos, next_state)));
}