AtCoder Beginner Contest 325振り返り

A - Takahashi san

読み出し、２つ目は不要

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問題あとで振り返ってみれば解けそうだった。