🐷
AtCoder Beginner Contest 325振り返り
A - Takahashi san
読み出し、2つ目は不要
use proconio::input;
fn main() {
input! {
a: String,
_b: String,
}
println!("{} san", a);
}
B - World Meeting
1時間ずつ試していけばいい。B問題は多くの場合総当たりで解ける。
use proconio::{derive_readable, input};
fn main() {
#[derive_readable]
#[derive(Debug)]
struct WX {
w: usize,
x: usize,
}
input! {
n: usize,
wx: [WX; n],
}
let result = (0..24)
.map(|t0| {
(0..n)
.map(|i| {
let t = (wx[i].x + t0) % 24;
if 9 <= t && t < 18 {
wx[i].w
} else {
0
}
})
.sum::<usize>()
})
.max()
.unwrap();
println!("{}", result);
}
C - Sensors
DFSで解く。UnionFindでも解けるらしい。
DFSしなくてもよいかと迷ったのが今回のミスで、ここまでしか解けなかった。
方針としては近傍に色を塗っていくだけ。
use itertools::iproduct;
use proconio::{input, marker::Chars};
fn in_range(y: usize, x: usize, dy: i64, dx: i64, h: usize, w: usize) -> Option<(usize, usize)> {
let ty = y as i64 + dy;
let tx = x as i64 + dx;
if tx < 0 || tx >= w as i64 || ty < 0 || ty >= h as i64 {
return None;
}
let ty = ty as usize;
let tx = tx as usize;
return Some((ty, tx));
}
fn main() {
input! {
h: usize,
w: usize,
s: [Chars; h],
}
let dirs = [
(-1, -1),
(-1, 0),
(-1, 1),
(0, -1),
(0, 1),
(1, -1),
(1, 0),
(1, 1),
];
struct S {
y: usize,
x: usize,
}
let mut color = 0;
let mut memo = vec![vec![0; w]; h];
for (y, x) in iproduct!(0..h, 0..w) {
if memo[y][x] != 0 {
continue;
}
if s[y][x] != '#' {
continue;
}
color += 1;
let mut stack = vec![S { y, x }];
while let Some(S { y, x }) = stack.pop() {
if memo[y][x] != 0 {
continue;
}
memo[y][x] = color;
for &(dy, dx) in dirs.iter() {
if let Some((y, x)) = in_range(y, x, dy, dx, h, w) {
if s[y][x] != '#' {
continue;
}
stack.push(S { y, x });
}
}
}
}
println!("{}", color);
}
UnionFindを使うとこうなる
use itertools::iproduct;
use petgraph::unionfind::UnionFind;
use proconio::{input, marker::Chars};
use std::collections::HashSet;
fn in_range(y: usize, x: usize, dy: i64, dx: i64, h: usize, w: usize) -> Option<(usize, usize)> {
let ty = y as i64 + dy;
let tx = x as i64 + dx;
if tx < 0 || tx >= w as i64 || ty < 0 || ty >= h as i64 {
return None;
}
let ty = ty as usize;
let tx = tx as usize;
return Some((ty, tx));
}
fn main() {
input! {
h: usize,
w: usize,
s: [Chars; h],
}
let sensors: Vec<_> = iproduct!(0..h, 0..w)
.filter(|&(y, x)| s[y][x] == '#')
.collect();
if sensors.len() == 0 {
println!("{}", 0);
return;
}
let mut yx_to_idx = vec![vec![None; w]; h];
for (i, &(y, x)) in sensors.iter().enumerate() {
yx_to_idx[y][x] = Some(i);
}
let mut uf = UnionFind::new(sensors.len());
let dirs = [
(-1, -1),
(-1, 0),
(-1, 1),
(0, -1),
(0, 1),
(1, -1),
(1, 0),
(1, 1),
];
for (i, &(y0, x0)) in sensors.iter().enumerate() {
for &(dy, dx) in dirs.iter() {
if let Some((y, x)) = in_range(y0, x0, dy, dx, h, w) {
if let Some(j) = yx_to_idx[y][x] {
uf.union(i, j);
}
}
}
}
let ans = uf
.into_labeling()
.iter()
.collect::<HashSet<_>>()
.len();
println!("{}", ans);
}
D - Printing Machine
貪欲法で解ける。賞味期限が近いやつから食っていく。
解説を見てみれば何も難しくない、解けたはずの問題だった。
BinaryHeapでPriorityQueueを実現できるが、昇順で値を取得したい場合は Reverse
すること。
use std::{
cmp::Reverse,
collections::BinaryHeap,
};
use proconio::{derive_readable, input};
fn main() {
#[derive_readable]
#[derive(Debug)]
struct TD {
t: usize,
d: usize,
}
input! {
n: usize,
td: [TD; n],
}
let mut v = Vec::from_iter(td.iter().map(|&TD { t, d }| (t, t + d)));
v.sort_by(|&(at, _atd), &(bt, _btd)| at.cmp(&bt));
let mut pq = BinaryHeap::new();
let mut it = 0;
let mut t = 0;
let mut ans = 0;
loop {
if pq.is_empty() {
if it == n {
break;
}
t = v[it].0;
}
while it < n && v[it].0 == t {
pq.push(Reverse(v[it].1));
it += 1;
}
while let Some(td) = pq.peek() {
if td.0 >= t {
break;
}
pq.pop();
}
if !pq.is_empty() {
pq.pop();
ans += 1;
}
t += 1;
}
println!("{}", ans);
}
E - Our clients, please wait a moment
ダイクストラ法の実装があるので簡単。
出発地点からのコストと、到達地点からのコストを事前に計算しておく
use itertools::iproduct;
use petgraph::{algo::*, graph::*};
use proconio::input;
fn main() {
input! {
n: usize,
a: usize,
b: usize,
c: usize,
d: [[usize; n]; n]
}
let g_car: Graph<usize, usize, petgraph::Undirected, usize> =
UnGraph::from_edges(iproduct!(0..n, 0..n).map(|(i, j)| (i, j, a * d[i][j])));
let g_train: Graph<usize, usize, petgraph::Undirected, usize> =
UnGraph::from_edges(iproduct!(0..n, 0..n).map(|(i, j)| (i, j, b * d[i][j] + c)));
let cars = dijkstra(&g_car, node_index(0), None, |e| *e.weight());
let trains = dijkstra(&g_train, node_index(n - 1), None, |e| *e.weight());
let result = (0..n)
.map(|i| {
let i = node_index(i);
cars[&i] + trains[&i]
})
.min()
.unwrap();
println!("{}", result);
}
総括
C問題、DFSを素直にやればよかった。
DE問題あとで振り返ってみれば解けそうだった。
Discussion