ABC413: Rustで解く！問題解説
AtCoder Beginner Contest 413のA-E問題をRustで解いた際の解法をまとめました。
A 問題
問題
解説
各荷物のサイズを表す配列 Yes 、そうでなければ No を出力します。
コード
use proconio::input;
fn main() {
// 入力
input! {
n: usize, // 品物の個数
m: usize, // サイズ制限
a: [usize; n], // 品物のサイズリスト
}
// 配列aの合計値を求める
let a_sum: usize = a.iter().sum();
// 合計値がM以下ならYes、そうでないならNoを出力
println!("{}", if a_sum <= m { "Yes" } else { "No" });
}
B 問題
問題
解説
異なる文字列を2つ選んで作ることができる文字列の種類数を求める問題です。
入力として与えられる文字列のリストから、異なる2つの文字列を選びます。その後、選んだ2つの文字列を順番に繋げて新しい文字列を作ります。この時作成した文字列を重複なく管理するために、 HashSet を使用します。
最終的に HashSet に格納された文字列の種類数が答えとなります。
コード
use proconio::input;
use std::collections::HashSet;
fn main() {
// 入力
input! {
n: usize, // 文字列の数
s: [String; n], // 文字列のリスト
}
// 連結後の文字列の集合
let mut ans = HashSet::new();
// 2つの文字列の繋げ方を全て試す
for i in 0..n {
for j in 0..n {
// 同じ文字列2つは繋げない
if i == j { continue; }
// 連結後の文字列を追加
let concatenated = (s[i].clone() + &s[j].clone()).to_string();
ans.insert(concatenated);
}
}
// 連結後の文字列の種類数を答える
println!("{}", ans.len());
}
C 問題
問題
解説
キューにまとめて要素を追加したり、指定個数を取り出して合計値を出力したりする問題です。
この問題では、以下の2種類のクエリを処理します。
- クエリ1：値が同じ要素を指定された個数だけキューに追加します。
- クエリ2：キューから指定個数分の要素を取り出し、その合計値を計算して出力します。
クエリ1では、個数と値のペアをキューの末尾に入れて同じ値の要素をまとめて管理します。
クエリ2では、キューの先頭から指定個数分の要素を取り出し合計値を出力します。取り出した個数が指定個数を超えた場合、その超過分をキューの先頭に戻します。
コード
use proconio::input;
use std::collections::VecDeque;
fn main() {
// 入力
input! {
q: usize, // クエリ数
}
let mut dq = VecDeque::new();
// クエリの入力
for _ in 0..q {
input! {
nm: usize, // クエリ番号
}
if nm == 1 {
// クエリ1: (追加する個数, 値)をキューの末尾に追加
input! {
cnt: usize, // 個数
x: usize, // 値
}
dq.push_back((cnt, x));
} else {
// クエリ2: K個分の値を取り出して、合計値を求める
input! {
k: usize, // 取得する個数
}
// 合計値
let mut tot_val = 0;
// 取り出す個数の残り
let mut rest_k = k;
// 1つずつ取り出して、合計値と残りの個数を更新
while let Some((cnt, val)) = dq.pop_front() {
// 合計K個以上になった場合
if cnt >= rest_k {
// 取り出す必要がある個数 * 値を合計値に加える
tot_val += rest_k * val;
// (戻す個数, 値)をキューの先頭に追加
dq.push_front((cnt - rest_k, val));
break;
} else {
// 合計K個を超えない場合
tot_val += cnt * val;
rest_k -= cnt;
}
}
// 合計値を出力
println!("{}", tot_val);
}
}
}
D 問題
問題
解説
与えられた数列を並び替えて等比数列が作れるかどうかを判定する問題です。
まず、数列の要素を正の数と負の数に分けます。その後、以下の3つのケースに分けて考えます。
-
全ての要素が正または全て負の場合
この場合、絶対値が小さい順に並べると等比数列になる可能性があります。並べた後に等比数列であるかを判定します。 -
正の個数と負の個数の差が2個以上の場合
この場合、どのように並び替えても等比数列を作ることはできません。 -
正の個数と負の個数の差が1個以下の場合
この場合、絶対値が小さい順に正の数と負の数を交互に並べると等比数列になる可能性があります。正の個数と負の個数が同じ場合は、正の数を先に並べる場合と、負の数を先に並べる場合の両方を試します。どちらかで等比数列が作れるかを判定します。
等比数列の判定については浮動小数点数の誤差を避けるため、両辺の分母の値をかけて式変形した後、整数演算で判定します。
コード
use proconio::input;
fn main() {
// テストケース数の入力
input! {
t: usize,
}
for _ in 0..t {
solve();
}
}
fn solve() {
input! {
n: usize,
a: [i64; n],
}
// 正と負の2つのグループに分ける
let mut groups = part_plus_minus(&a);
// 正は昇順、負は降順にする
groups[0].sort();
groups[1].sort_by(|a, b| b.cmp(a));
// 正のみ
if groups[1].len() == 0 {
println!("{}", if is_geometric(&groups[0]) { "Yes" } else { "No" });
}
// 負のみ
else if groups[0].len() == 0 {
println!("{}", if is_geometric(&groups[1]) { "Yes" } else { "No" });
}
// 正と負が混在
else {
// 正の個数と負の個数の差が2個以上異なる場合は不可
if groups[0].len().abs_diff(groups[1].len()) >= 2 {
println!("No");
return;
}
// 正を先にして交互に並べる
if groups[0].len() >= groups[1].len() {
let arr = make_mix_array(&groups[0], &groups[1], groups[0].len());
if is_geometric(&arr) {
println!("Yes");
return;
}
}
// 負を先にして交互に並べる
if groups[1].len() >= groups[0].len() {
let arr = make_mix_array(&groups[1], &groups[0], groups[1].len());
if is_geometric(&arr) {
println!("Yes");
return;
}
}
// どちらも出来ない場合は不可
println!("No");
}
}
// 数列を正の数と負の数に分ける
fn part_plus_minus(a: &Vec<i64>) -> Vec<Vec<i64>> {
let mut plus_minus = vec![Vec::new(); 2];
for &aa in a {
if aa > 0 {
plus_minus[0].push(aa);
} else {
plus_minus[1].push(aa);
}
}
plus_minus
}
// 等比数列かどうかを判定する
fn is_geometric(vec: &Vec<i64>) -> bool {
let ck_sz = vec.len() - 2;
for i in 0..ck_sz {
if vec[i] * vec[i + 2] != vec[i + 1] * vec[i + 1] {
return false;
}
}
true
}
// 正と負を交互に並べた配列を作成する
fn make_mix_array(first: &Vec<i64>, second: &Vec<i64>, large_sz: usize) -> Vec<i64> {
let mut arr = Vec::new();
for i in 0..large_sz {
arr.push(first[i]);
// 配列サイズを超える場合はスキップ
if i == second.len() {
continue;
}
arr.push(second[i]);
}
arr
}
E 問題
問題
解説
この問題は、
-
a,b -
N=3 - この時、
a=0, b=2 (p0,p1,p2,p3) (p3,p2,p1,p0)
-
カードの反転は以下のように考えていくと、昇順にすることができます。
-
反転の優先順位
範囲が広い反転を先に行うことで、後の調整が容易になります。そのため、最初に全体を2つの部分に分けて、前半と後半を比較します。 -
反転の条件
前半部分と後半部分の最小値を比較し、後半部分の最小値が前半部分の最小値より小さい場合は、全体を反転させます。これにより、最小値が前半部分に来るようにします。 -
再帰的な処理
一度調べた後は、現在の範囲をさらに半分に分割し、同様の処理を再帰的に行います。これを範囲が1枚になるまで繰り返します。
最後に、反転後のカードの並びを出力します。
コード
use itertools::Itertools;
use proconio::input;
fn main() {
// テストケース数の入力
input! {
t: usize,
}
for _ in 0..t {
solve();
}
}
fn solve() {
// 入力
input! {
n: usize,
mut p: [usize; 1 << n],
}
let sz = 1 << n;
// 再帰的に入れ替えを実施
rec(0, sz / 2, sz, &mut p);
// 入れ替え後の配列を出力
println!("{}", p.iter().join(" "));
}
fn rec(left_spos: usize, right_spos: usize, sz: usize, arr: &mut Vec<usize>) {
// 全体サイズが1個なら終了
if sz == 1 {
return;
}
// 前半のsz/2個の最小値
let left_min: usize = *arr[left_spos..left_spos + sz / 2].iter().min().unwrap();
// 後半のsz/2個の最小値
let right_min: usize = *arr[right_spos..right_spos + sz / 2].iter().min().unwrap();
// 後半に小さい値があれば、全反転する
if left_min > right_min {
let mut tmp_arr = arr[left_spos..left_spos + sz].to_vec();
tmp_arr.reverse();
for i in 0..sz {
arr[left_spos + i] = tmp_arr[i];
}
}
// 範囲をさらに前半、後半に分解して、再帰的に調べる
rec(left_spos, left_spos + sz / 4, sz / 2, arr);
rec(right_spos, right_spos + sz / 4, sz / 2, arr);
}
Discussion