概要
Atcoder Beginner Contestの437をRustで解きました。
コンテスト中にA-Fがとけたので振り返りで書きます。
A問題
計算問題です。
fn main() {
input! {
a: usize,
b: usize
}
println!("{}", a * 12 + b);
}
B問題
各行に対して、Bに含まれた数字が何個入っているかを数えて、その最大値を答える問題です。
制約がちっちゃいので何をしても間に合います。
fn main() {
input! {
h: usize,
w: usize,
n: usize,
a: [[usize; w]; h],
b: [usize; n]
}
let ans = a.iter().fold(0, |acc, now| {
let cur = now.iter().filter(|&&e| b.contains(&e)).count();
max(acc, cur)
});
println!("{}", ans);
}
C問題
最初にトナカイを全てソリに乗せます。
その後に一番効率よいトナカイから引く側に引き抜きます。
効率よいトナカイがどんなトナカイかと考えると、
1頭引き抜くことで、ソリの重さがw[i]だけ軽くなり、引く力がp[i]だけ強くなります。
そのため、1頭引き抜くことでw[i] + p[i]だけ引く側が得する状態になるのです。
そのため、w[i] + p[i]が大きい順に引き抜けばいいことがわかります。
あとはこれを引く力が重さよりも大きくなるまで引き抜いてあげればいいです。
fn solve() {
input! {
n: usize,
wp: [(usize, usize); n]
}
let mut w = wp.iter().map(|e| e.0).sum::<usize>();
let mut p = 0;
let mut ans = n;
let mut heap = BinaryHeap::new();
for (idx, &(w, p)) in wp.iter().enumerate() {
heap.push((w + p, idx));
}
while w > p {
let (_, idx) = heap.pop().unwrap();
let (ww, pp) = wp[idx];
w -= ww;
p += pp;
ans -= 1;
}
println!("{}", ans);
}
D問題
Aiの方がBjよりも大きい時とそうでない時がわかれば絶対値が外れて計算しやすくなります。
そこで、Aiを固定して考えることでBをまとめて計算できるので、累積和的に計算することができます。
Bはソートする必要があることに注意してください。
pub use prefix_sum_1d::*;
mod prefix_sum_1d {
use std::ops::{Add, Bound, Range, RangeBounds, Sub};
use num::Zero;
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct PrefixSum1D<T> {
acc: Vec<T>,
}
impl<T> PrefixSum1D<T>
where
T: Zero + Clone + Copy + Add<Output = T> + Sub<Output = T>,
{
pub fn new(xs: &[T]) -> Self {
let mut acc = vec![T::zero()];
for &x in xs.iter() {
let &la = acc.last().unwrap();
acc.push(la + x);
}
Self { acc }
}
pub fn range_sum(&self, range: impl RangeBounds<usize>) -> T {
let range = self.get_range(range);
let end = self.acc[range.end];
let start = self.acc[range.start];
end - start
}
fn get_range(&self, range: impl RangeBounds<usize>) -> Range<usize> {
let begin = match range.start_bound() {
Bound::Unbounded => 0,
Bound::Included(&x) => x,
Bound::Excluded(&x) => x + 1,
};
let end = match range.end_bound() {
Bound::Excluded(&x) => x,
Bound::Included(&x) => x + 1,
Bound::Unbounded => self.acc.len() - 1,
};
begin..end
}
}
}
fn main() {
input! {
n: usize,
m: usize,
a: [isize; n],
mut b: [isize; m]
}
b.sort();
let c = PrefixSum1D::new(&b);
let mut ans = ModInt998244353::new(0);
for &num in a.iter() {
let low = b.upper_bound(&num);
let res = m - low;
let l = c.range_sum(..low);
let lans = low as isize * num - l;
let r = c.range_sum(low..);
let rans = r - res as isize * num;
let cur = lans + rans;
ans += cur;
}
println!("{}", ans);
}
E問題
Aを辞書順に並べます。Trie木的に木を構築して、DFSしていけば良さそうです。
同じ配列になる時は同じidになるように構築するところが一番難しいですが、
pid[i] := x番目の配列のID として、その先にyをappendした配列はすべて一致するので、
それをmpという変数で管理することでこれを実現しています。
fn dfs(v: usize, to: &Vec<Vec<(usize, usize)>>, mp2: &HashMap<usize, Vec<usize>>, ans: &mut Vec<usize>) {
let vs = mp2.get(&v).map(|v| v.as_slice()).unwrap_or(&[]);
for &idx in vs.iter() {
ans.push(idx);
}
for &(_, idx) in to[v].iter() {
dfs(idx, to, mp2, ans);
}
}
fn main() {
input! {
n: usize,
xy: [(usize, usize); n]
}
let mut pid = vec![0; n + 1];
let mut to = vec![vec![]; n + 1];
let mut mp = HashMap::new();
let mut mp2 = HashMap::new();
let mut id = 1;
for i in 0..n {
let (x, y) = xy[i];
let p = pid[x];
let key = (p, y);
let v = if mp.contains_key(&key) {
let &id = mp.get(&key).unwrap();
id
} else {
mp.insert(key, id);
to[p].push((y, id));
id += 1usize;
id - 1
};
pid[i + 1] = v;
mp2.entry(v).or_insert(Vec::new()).push(i + 1);
}
for i in 0..=n {
to[i].sort_by_key(|&e| e.0);
}
let mut ans = vec![];
dfs(0, &to, &mp2, &mut ans);
println!("{}", ans.iter().join(" "));
}
F問題
マンハッタン距離は座標系を45degすることで回転後のx座標、y座標がマンハッタン距離そのものになり、とても扱いやすくなります。
よって、ある座標からのマンハッタン距離の最大値を求めたい時は x軸、y軸の最大・最小を素早く計算することができればそのdiffがマンハッタン距離となるため、
最大距離がすぐに求められます。
セグ木を使えば区間最小・最大を高速に求めることができるのでこの問題もとけます。
fn main() {
input! {
n: usize,
q: usize,
xy: [(isize, isize); n],
}
let f = |xy: (isize, isize)| {
let (x, y) = xy;
(x - y, x + y)
};
let mut xmax: Segtree<Max<isize>> = Segtree::new(n);
let mut xmin: Segtree<Min<isize>> = Segtree::new(n);
let mut ymax: Segtree<Max<isize>> = Segtree::new(n);
let mut ymin: Segtree<Min<isize>> = Segtree::new(n);
for (idx, &(x, y)) in xy.iter().enumerate() {
let (x, y) = f((x, y));
xmax.set(idx, x);
xmin.set(idx, x);
ymax.set(idx, y);
ymin.set(idx, y);
}
for _ in 0..q {
input! {
t: usize
}
if t == 1 {
input! {
idx: Usize1,
x: isize,
y: isize
}
let (x, y) = f((x, y));
xmax.set(idx, x);
xmin.set(idx, x);
ymax.set(idx, y);
ymin.set(idx, y);
} else {
input! {
l: Usize1,
r: usize,
x: isize,
y: isize
}
let (x, y) = f((x, y));
let a1 = xmax.prod(l..r);
let a2 = xmin.prod(l..r);
let a3 = ymin.prod(l..r);
let a4 = ymax.prod(l..r);
let ans = max(a1.abs_diff(x), a2.abs_diff(x))
.max(a3.abs_diff(y))
.max(a4.abs_diff(y));
println!("{}", ans);
}
}
}
おわりに
2025年のABCも来週が最後ですね。最後まで楽しみたいと思います！！