blog.bouzuya.net

2023-10-23 PAST 本上級を読み終えた / ABC220 A, B, C, D, F

今日気づいたのだけど、昨日で PAST 本 (『アルゴリズム実技検定　公式テキスト［上級］～［エキスパート］編』)を読み終えていた。 https://book.mynavi.jp/ec/products/detail/id=135840 。 2023-05-29 から 5 ヶ月かかっている。

上級・エキスパートは自力ではほとんど解けなかった。ストレッチゾーンという感じで良かったように思う。

次はしばらく ISUCON 関連のことと業務関連のあれこれかな……。今週は Slay the Spire を控えようと思っている。

昨日 (2023-10-22) の記事に下の子のおしりたんていのことを書いておいた。おしりたんていの終わりの問いかけに毎回「たのしかったー」とこたえるのはさすがに素直すぎて怖い。 Prime Video で同じシーズンをもう 4 周くらいは観ているのに、だよ……？

bouzuya/tsukota を Pixel 7 から Pixel 8 に移行した。端末間の引き継ぎをもっと簡単にしたいな……。 Android の標準のバックアップに頼るのも手だけど……。

ABC220 : AtCoder Beginner Contest 220

use std::collections::VecDeque;

use proconio::{input, marker::Usize1};

fn dfs(edges: &[Vec<usize>], depth: &mut [usize], size: &mut [usize], u: usize, p: usize) {
    depth[u] = depth[p] + 1;
    let mut s = 1_usize;
    for v in edges[u].iter().copied() {
        if v == p {
            continue;
        }
        dfs(edges, depth, size, v, u);
        s += size[v];
    }
    size[u] = s;
}

fn main() {
    input! {
        n: usize,
        uv: [(Usize1, Usize1); n - 1],
    };

    let mut edges = vec![vec![]; n];
    for (u, v) in uv {
        edges[u].push(v);
        edges[v].push(u);
    }

    let inf = 1_usize << 60;

    let mut depth = vec![0; n];
    let mut size = vec![inf; n];
    dfs(&edges, &mut depth, &mut size, 0, 0);

    let mut ans = vec![inf; n];
    ans[0] = depth.iter().sum::<usize>() - n;

    let mut deque = VecDeque::new();
    deque.push_back(0);
    while let Some(u) = deque.pop_front() {
        for v in edges[u].iter().copied() {
            if ans[v] != inf {
                continue;
            }
            deque.push_back(v);
            ans[v] = ans[u] + (n - size[v]) - size[v];
        }
    }

    for a in ans {
        println!("{}", a);
    }
}

今日のコミット。