ABC406: Rustで解く！問題解説
AtCoder Beginner Contest 406のA-E問題をRustで解いた際の解法をまとめました。
A 問題
問題
解説
この問題は、締め切り時刻と提出時刻を比較し、締め切り前に提出できたかを判定する問題です。
まず、締め切り時刻と提出時刻をそれぞれ分単位に変換します。その後、締め切り時刻 Yes 、そうでない場合は No を出力します。
コード
use proconio::input;
fn main() {
// 入力
input! {
a: usize, // 締め切り時刻の時
b: usize, // 締め切り時刻の分
c: usize, // 提出時刻の時
d: usize // 提出時刻の分
}
// 時刻を分に変換
let deadline = a * 60 + b;
let submit = c * 60 + d;
// 締め切り時刻と提出時刻を比較して結果を出力
println!("{}", if deadline >= submit { "Yes" } else { "No" });
}
B 問題
問題
解説
この問題では、数列
ただし、掛け算の結果が
注意点として、掛け算の結果が 64bit の最大値を超える可能性があるため、128bit 型の変数を使用して計算を行います。また、
コード
use proconio::input;
fn main() {
// 入力
input! {
n: usize, k: usize,
a: [u128; n],
}
// 10^kを求める
let limit = power(10, k) as u128;
let mut cur = 1u128;
// 数列の値を順番に掛け算
for aa in a {
if cur * aa >= limit {
// 掛け算結果が上限以上になった場合、1にリセット
cur = 1;
} else {
cur *= aa;
}
}
// 出力
println!("{}", cur);
}
// x^k を計算する関数
fn power(x: usize, k: usize) -> usize {
let mut ret = 1;
for _ in 0..k {
ret *= x;
}
ret
}
C 問題
問題
解説
この問題では、数列
具体的には、指定した範囲の要素間の差が「増加→減少→増加」の順となっているものの個数を以下1~3の手順で求めます。
-
数列の隣接する要素間の差を調べ、前の値より大きい場合は
'<'、小さい場合は'>'として記録します。 -
この
'<'と'>'の列をランレングス圧縮を用いて、(種類, 個数) のペア型で表します。
ランレングス圧縮とは、連続する同じ文字を1つのグループとしてまとめる手法です。 -
圧縮された列の中から、
'<', '>', '<'の形を持つ部分を探します。このとき、左側の'<'の個数と右側の'<'の個数を掛け合わせて、その総和を求めます。
コード
use proconio::{input, marker::Usize1};
fn main() {
// 入力
input! {
n: usize,
p: [Usize1; n],
}
// 隣接する要素間の差を記録
let mut diffs = Vec::new();
for i in 0..n-1 {
if p[i] < p[i+1] { diffs.push('<');}
else { diffs.push('>');}
}
// '<''>'をランレングス圧縮する
let rungs = runglen(&diffs);
// サイズが3未満の場合は0
if rungs.len() < 3 {
println!("0");
return;
}
// '<','>','<'を見つけて、個数を計算
let mut ans = 0;
for i in 0..rungs.len()-2 {
if rungs[i].0 == '<' && rungs[i+1].0 == '>' && rungs[i+2].0 == '<' {
ans += rungs[i].1 * rungs[i+2].1;
}
}
// 出力
println!("{}", ans);
}
// ランレングス圧縮
pub fn runglen(arr: &Vec<char>) -> Vec<(char, usize)> {
let len = arr.len();
let mut arr_ret = Vec::new();
let mut tail = 0;
let mut top = 0;
while tail < len {
let now_c = arr[tail];
while top < len && now_c == arr[top] {
top += 1;
}
arr_ret.push((now_c, top - tail));
tail = top;
}
arr_ret
}
D 問題
問題
解説
この問題は、指定された行または列にあるゴミの個数を出力し、その後その行または列に含まれるゴミを取り除く操作を行う問題です。
ゴミの座標を行ごと、列ごとに独立して管理し、クエリに応じて適切な操作を行います。
-
クエリ1の場合
指定された行に含まれるゴミの個数を出力し、その行に含まれるゴミを列方向のデータ構造からも削除します。 -
クエリ2の場合
指定された列に含まれるゴミの個数を出力し、その列に含まれるゴミを行方向のデータ構造からも削除します。
行と列のデータ構造を相互に更新することで、効率的にクエリを処理します。
コード
use proconio::{input, marker::Usize1};
use std::collections::HashSet;
fn main() {
// 入力
input! {
h: usize, w: usize, n: usize,
}
// ゴミの座標を行ごと、列ごとに管理
let mut row = vec![HashSet::new(); h];
let mut col = vec![HashSet::new(); w];
input_garbage(n, &mut row, &mut col);
// クエリの処理
input! {
q: usize,
}
for _ in 0..q {
input! {
query_type: usize,
}
if query_type == 1 {
remove_row(&mut row, &mut col);
} else {
remove_col(&mut row, &mut col);
}
}
}
// ゴミの座標を入力し、行と列のデータ構造に登録
fn input_garbage(n: usize, row: &mut Vec<HashSet<usize>>, col: &mut Vec<HashSet<usize>>) {
for _ in 0..n {
input! {
x: Usize1, y: Usize1,
}
row[x].insert(y);
col[y].insert(x);
}
}
// 指定された行のゴミを取り除く
fn remove_row(row: &mut Vec<HashSet<usize>>, col: &mut Vec<HashSet<usize>>) {
input! {
x: Usize1,
}
// 指定された行に残っているゴミの個数を出力
println!("{}", row[x].len());
// 行に含まれるゴミを列のデータ構造から削除
for &item in &row[x] {
col[item].remove(&x);
}
// 行のデータを空にする
row[x] = HashSet::new();
}
// 指定された列のゴミを取り除く
fn remove_col(row: &mut Vec<HashSet<usize>>, col: &mut Vec<HashSet<usize>>) {
input! {
y: Usize1,
}
// 指定された列に残っているゴミの個数を出力
println!("{}", col[y].len());
// 列に含まれるゴミを行のデータ構造から削除
for &item in &col[y] {
row[item].remove(&y);
}
// 列のデータを空にする
col[y] = HashSet::new();
}
E 問題
問題
解説
この問題では、
※popcountとは、整数を二進数表記した際に1となっているビットの個数を指します。
この問題を解くために、動的計画法（DP）を用いて以下の値を計算します。
-
dp\_cur[j] j -
dp\_tot[j] j
DPの遷移は以下のように行います。
-
N - 0を選択する場合
next\_dp\_cnt[j] += cur\_dp\_cnt[j] next\_dp\_tot[j] += cur\_dp\_tot[j]
- 1を選択する場合
next\_dp\_cnt[j+1] += cur\_dp\_cnt[j] next\_dp\_tot[j+1] += cur\_dp\_tot[j] + cur\_dp\_cnt[j] \times (i ビット目の値)
- 0を選択する場合
-
N - 0を選択する場合
next\_dp\_cnt[j] += 1 next\_dp\_tot[j] += 現在の値
- 0を選択する場合
最終的に、DPで計算した
コード
use proconio::input;
use std::mem::swap;
const BITSZ: usize = 60;
const MOD: u128 = 998244353;
fn main() {
// テストケース数を入力
input! {
t: usize,
}
for _ in 0..t {
solve();
}
}
fn solve() {
// 各テストケースの入力
input! {
n: u128,
k: usize,
}
// 計算結果を出力
println!("{}", calc(n, k));
}
fn calc(n: u128, k: usize) -> u128 {
// dp[j] = 0以上N未満の、1が立っている個数jの個数と総和
let mut cur_dp_cnt = vec![0usize; BITSZ + 1];
let mut cur_dp_tot = vec![0u128; BITSZ + 1];
// 現在のpopcountと値
let mut cur_pop_cnt = 0usize;
let mut cur_num = 0u128;
// 上位ビットから順に処理
for i in 0..BITSZ {
let mut next_dp_cnt = vec![0usize; BITSZ + 1];
let mut next_dp_tot = vec![0u128; BITSZ + 1];
// 現在のビットのマスク
let mask = 1u128 << (BITSZ - 1 - i);
// N未満の遷移
trans_dp_less(
&cur_dp_cnt,
&cur_dp_tot,
&mut next_dp_cnt,
&mut next_dp_tot,
mask,
);
// 現在のビットが1の場合のみ
if n & mask != 0 {
// Nの遷移
trans_dp_equal(
cur_pop_cnt,
cur_num,
&mut next_dp_cnt,
&mut next_dp_tot,
);
// 現在の値を更新
cur_pop_cnt += 1;
cur_num += mask;
}
// 現在のDPと次のDPを交換
swap(&mut cur_dp_cnt, &mut next_dp_cnt);
swap(&mut cur_dp_tot, &mut next_dp_tot);
}
// N自身がpopcount = Kの場合を加算
let mut result = cur_dp_tot[k];
if cur_pop_cnt == k {
result = (result + n) % MOD;
}
result
}
fn trans_dp_less(
cur_dp_cnt: &Vec<usize>,
cur_dp_tot: &Vec<u128>,
next_dp_cnt: &mut Vec<usize>,
next_dp_tot: &mut Vec<u128>,
mask: u128,
) {
for j in 0..BITSZ {
// 0を選択時
next_dp_cnt[j] += cur_dp_cnt[j];
next_dp_tot[j] += cur_dp_tot[j];
next_dp_tot[j] %= MOD;
// 1を選択時
next_dp_cnt[j + 1] += cur_dp_cnt[j];
next_dp_tot[j + 1] += cur_dp_tot[j] + cur_dp_cnt[j] as u128 * mask;
next_dp_tot[j + 1] %= MOD;
}
}
fn trans_dp_equal(
cur_pop_cnt: usize,
cur_num: u128,
next_dp_cnt: &mut Vec<usize>,
next_dp_tot: &mut Vec<u128>,
) {
// 0を選択時
next_dp_cnt[cur_pop_cnt] += 1;
next_dp_tot[cur_pop_cnt] += cur_num;
next_dp_tot[cur_pop_cnt] %= MOD;
}
Discussion