blog.bouzuya.net

2023-05-26 『チームトポロジー』を読んだ / PAST #1 J を解いた

『チームトポロジー』を読んだ。コンウェイの法則についてはそうだろうなと思うんだけど、この本のチームタイプやインタラクションモードなどはそこまでピンと来ていない。

Rust をやるぞ。

明日で PAST 中級本の問題が終わるので、次を買う。

  • PAST #1 J - 地ならし(第一回アルゴリズム実技検定 J問題) https://atcoder.jp/contests/past201912-open/tasks/past201912_j
    • https://atcoder.jp/contests/past201912-open/submissions/41708232
    • A_h1 から A_hw への最短距離、 A_hw から A_1w の最短距離を求めると、途中の重なっている経路を求めるのが難しいし、すでに通ったところにコストがかからないことが考慮されないので全体として最短距離にならなくなってしまう
    • そこで A_h1, A_hw, A_1w のそれぞれからすべての点までの最短距離を求めておき、 3 つの点からある中継地点までの距離を求める
    • 中継地点は全探索しても十分間に合う
    • 中継地点が A_hw になるとき、最初の誤った解法と答えが一致する
use std::{cmp::Reverse, collections::BinaryHeap};

use proconio::input;

fn main() {
    input! {
        h: usize,
        w: usize,
        a: [[usize; w]; h],
    }

    let inf = 1_usize << 60;
    let f = |dist: &mut Vec<Vec<usize>>, i: usize, j: usize| {
        let mut pq = BinaryHeap::new();
        pq.push((Reverse(0), (i, j)));
        dist[i][j] = 0;
        while let Some((Reverse(d), (i, j))) = pq.pop() {
            if dist[i][j] < d {
                continue;
            }
            let dir = vec![(-1, 0), (0, -1), (0, 1), (1, 0)];
            for (dr, dc) in dir {
                let (nr, nc) = (i as i64 + dr, j as i64 + dc);
                if !(0..h as i64).contains(&nr) || !(0..w as i64).contains(&nc) {
                    continue;
                }
                let (nr, nc) = (nr as usize, nc as usize);
                if dist[nr][nc] > dist[i][j] + a[nr][nc] {
                    dist[nr][nc] = dist[i][j] + a[nr][nc];
                    pq.push((Reverse(dist[nr][nc]), (nr, nc)));
                }
            }
        }
    };

    let mut dist_h1 = vec![vec![inf; w]; h];
    f(&mut dist_h1, h - 1, 0);

    let mut dist_hw = vec![vec![inf; w]; h];
    f(&mut dist_hw, h - 1, w - 1);

    let mut dist_1w = vec![vec![inf; w]; h];
    f(&mut dist_1w, 0, w - 1);

    let mut min = inf;
    for i in 0..h {
        for j in 0..w {
            min = min.min(dist_h1[i][j] + dist_hw[i][j] + dist_1w[i][j] - 2 * a[i][j]);
        }
    }
    let ans = min;
    println!("{}", ans);
}

今日のコミット。