ABC395:Rustで解く!問題解説
AtCoder Beginner Contest 395のA~E問題をRustで解いた際の解法をまとめました。
A問題
問題
解説
数列
どの2項でも条件を満たす場合は Yes
、1箇所でも条件を満たさない箇所があれば、No
となります。
コード
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問題
問題
解説
各マスについて「端のマスへの最短距離」が偶数であれば #
、奇数であれば .
を出力します。「端のマスへの最短距離」を求める手順は以下1~3の通りです。
- 縦座標の「上部
への距離」と「下部(0) への距離」のうち、小さい方を選ぶ。(N-1) - 横座標の「左部
への距離」と「右部(0) への距離」のうち、小さい方を選ぶ。(N-1) - 1と2で得られた値の中で、小さい方を選ぶ。
コード
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問題
問題
解説
尺取り法を用いて解くことができます。
数列
コード
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問題
問題
解説
3種類のクエリに従い、鳩の移動と巣にいる鳩の位置を答えます。ただし、クエリ2で2つの巣の鳩を総入れ替えする処理をそのまま実装するとクエリ1つ当たりの計算量が
具体的な方法としては、各巣に対して箱を割り当てておきます。鳩は箱の中に入れるようにして、巣の入れ替えを行う際は箱ごと入れ替えを行うようにします。また、箱から巣の位置を特定するための情報も保持し、箱が入れ替わるタイミングで箱から見た巣の位置も変更します。
これらをまとめると、クエリ1〜3の操作は以下のように読み替えることができます。
- 巣の中にある箱に鳩を入れる。
- 2つの巣の箱を入れ替える。また、箱から見える巣の情報も入れ替える。
- 鳩が入っている箱から見える巣を答える。
以上により、クエリ1〜3の各計算量が
コード
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問題
問題
解説
ダイクストラ法のアルゴリズムを使用して問題を解決することができます。
入力のグラフの有向辺について、入力と同じ向きの辺を「表の辺」、逆向きの辺を「裏の辺」と呼ぶことにします。また同様に、辺の向きによって各頂点に2つの状態(表と裏)があると考えます。この有向辺および状態のグラフについて、頂点
移動する際は、「現在の頂点の状態(表裏)」と「移動する辺(表裏)」を考慮して、「移動距離」と「移動後の頂点の状態(表裏)」を決定します。
-
現在の頂点の状態が表、移動する辺が表の場合
→ 移動距離は 、移動後の頂点の状態は表1 -
現在の頂点の状態が表、移動する辺が裏の場合
→ 移動距離は 、移動後の頂点の状態は裏x+1 -
現在の頂点の状態が裏、移動する辺が表の場合
→ 移動距離は 、移動後の頂点の状態は表x+1 -
現在の頂点の状態が裏、移動する辺が裏の場合
→ 移動距離は 、移動後の頂点の状態は裏1
頂点
コード
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)));
}
Discussion