ABC388:Rustで解く!問題解説
AtCoder Beginner Contest 388のA~E問題をRustで解いた際の解法をまとめました。
A問題
- 問題
- 解説
UPC
を付け加えた文字列を出力します。
- コード
use proconio::{input, marker::Chars};
fn main() {
input!{
s: Chars,
}
println!("{}UPC", s[0]);
}
B問題
- 問題
- 解説
ヘビの重さは、太さ × (元々の長さ + 伸びた長さ
ここで
この計算を
- コード
use proconio::input;
use std::cmp::max;
fn main() {
input!{
n: usize, d: usize,
tl: [(usize, usize); n],
}
for k in 1..=d {
let mut ans = 0;
for &(t, l) in &tl {
ans = max(t * (l+k), ans);
}
println!("{}", ans);
}
}
C問題
- 問題
- 解説
餅を2つ選んだときの小さい方を
そこで探索方法を工夫します。
①を満たす個数は二分探索を使うことで
全体の時間計算量は
- コード
use proconio::input;
const INF: usize = 1 << 60;
fn main() {
input! {
n: usize,
a: [usize; n],
}
let mut ans = 0;
// aの各要素に対して処理を行う
for i in 0..n {
let val = a[i] / 2; // bの半分
let pos = below_bound(&a, val); // b / 2以下のaの個数をカウント
if pos == INF { continue; } // 異常値の場合はスキップ
ans += pos + 1; // 個数を加算
}
println!("{}", ans);
}
// 二分探索
// x以下の最大のposを返す。0番目より小さい値では異常値として、「1<<60」を返す
pub fn below_bound<T: std::cmp::PartialOrd>(vec: &Vec<T>, val: T) -> usize {
let mut l = 0;
let mut r = vec.len();
while r - l > 0 {
let m = (l + r) / 2;
if vec[m] <= val {
l = m + 1; // val以下の値を探す
} else {
r = m; // valより大きい値を探す
}
}
if l == 0 { INF } else { l - 1 } // 異常値の処理
}
D問題
- 問題
- 解説
N年後の石の個数を求めればよいので、石の増減に注目し以下のように問題を読み替えます。
番目の宇宙人は、①「前にいる何人から合計 i 個の石をもらい」、 x
②「連続する後ろの人全員(渡すことができる人数)分の合計個の石を渡す」。 y
よって、①による石の増加、②による石の減少をまとめて行うことができます。
ここで②による石の配り方ですが、imos法の考え方を用いて石の増減が生じる境界部分に注目します。
開始位置(A)を
累積和は各人について1度ずつ行う必要があるので、
①で石を受け取ったタイミングでその加算分を隣に伝播させる必要があります。
- コード
use proconio::input;
use std::cmp::min;
use itertools::Itertools;
fn main() {
input!{
n: usize,
mut a: [i64; n],
}
let mut add_array = vec![0i64; n+1];
for i in 0..n {
// 受け取り分取得
let get_val = add_array[i];
a[i] += get_val;
// 受け取り値を隣に伝播
add_array[i + 1] += get_val;
// 配れる人数yを決めて、配る
let y = min(a[i], (n - 1 - i) as i64);
a[i] -= y;
// 今の位置から、y人それぞれ+1
// imos法で開始と終了後だけを更新
add_array[i + 1] += 1;
add_array[i + (y + 1) as usize] -= 1;
}
println!("{}", a.iter().join(" "));
}
E問題
- 問題
- 解説
そのため、まず①「大きい
①、②のグループの要素を優先度付きキューにそれぞれ追加し、キューの先頭の要素を比較してペアにしていきます。
-
①の先頭の値 >= ②の先頭の値 * 2
ペアにできるので、両方取り出してペア数を します。+1 -
①の先頭の値 < ②の先頭の値 * 2
②で取り出した値をペアにする方法がないので、②の要素だけを取り出します。 -
コード
use proconio::input;
use std::collections::BinaryHeap;
fn main() {
input!{
n: usize,
a: [i64; n],
}
// aを半分ずつに分ける (奇数の場合、中央値を捨てる)
let mut small_hp = BinaryHeap::new(); // 小さい方の要素を格納するキュー
let mut large_hp = BinaryHeap::new(); // 大きい方の要素を格納するキュー
for i in 0..n/2 {
small_hp.push(a[i]); // 小さい方の要素を追加
large_hp.push(a[n-1-i]); // 大きい方の要素を追加
}
let mut ans = 0; // ペア数をカウントする変数
for _i in 0..n/2 {
// small_hpが空の場合はスキップ
if small_hp.len() == 0 { continue; }
// 大きい方から見てマッチングさせる
if large_hp.len() != 0 {
let large = *large_hp.peek().unwrap(); // 大きい方の先頭の値を取得
let small = *small_hp.peek().unwrap(); // 小さい方の先頭の値を取得
// 組み合わせられる場合
if small * 2 <= large {
ans += 1; // ペア数を+1
large_hp.pop().unwrap(); // 大きい方の要素を取り出す
small_hp.pop().unwrap(); // 小さい方の要素を取り出す
}
// 組み合わせられない場合
else {
small_hp.pop().unwrap(); // 小さい方の要素を取り出す
}
}
}
println!("{}", ans); // 結果を出力
}
Discussion