ABC391:Rustで解く!問題解説
AtCoder Beginner Contest 391のA~E問題をRustで解いた際の解法をまとめました。
A問題
- 問題
- 解説
N
は S
に、 S
は N
に、 E
は W
に、 W
は E
に変換します。
- コード
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問題
- 問題
- 解説
グリッド
- コード
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問題
- 問題
- 解説
シミュレーションを用いて解くことができます。ただし、各クエリで計算量が
-
1 P H
: 鳩 を巣P に移動させる。H
鳩が現在どの位置にいるのかを毎回探すと、1回あたりの計算量が
-
2
: 複数の鳩がいる巣の個数を出力する。
2匹以上の鳩がいる巣を探すと、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問題
- 問題
- 解説
各ブロックについて高さが低い順に配置し、列毎に①「下から
- ①の情報をもとに最下段のブロックを横に見ていき、全ての列にブロックがあればそれらをまとめて消し、それらのブロックの時刻に②「ブロックを消す直前の時刻の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問題
- 問題
- 解説
アルゴリズムとしては動的計画法(DP)を用いて、以下を求めることで問題を解決できます。
- 葉
を0または1にするための操作手数の最小値i
一番下の葉から順に、「3つの子の葉の組み合わせ
親の葉を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)
なお、最終的な答えについてですが、最初の文字列から
- コード
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