bouzuya.hatenablog.com

ぼうずやのにっき

食洗機が届いた / 『ハーモニー』を読んだ / PAST #8 M を解いた

昨日、食器洗い乾燥機 (食洗機) が届いた。 Panasonic の NP-TCR4-W 。

2017-03-18 に買ったものの調子が悪いので買い替えることにした。きちんと調べていないのだけど水温が上がっていないような気がしている。油汚れなどが落ちなくなってしまった。買ってから 6 年が経つし買い替えてもいいだろうと判断した。

2017 に買わなかったモデルを買った。価格は約 35,000 円。型落ちもいいところだけど過去のものに不満はないし何よりすぐほしいのとサイズも気にしたくないので同型は都合が良かった。

すごく良いと思うこともないし悪くもない。かごがワイヤーに変わったけどそれくらいだろうか……。一応機能は増えているけれど使う予定はない。 60,000 円のものを 6 年使ったので 35,000 なら 3 年くらいは使いたい。

『ハーモニー』を読んだ。いまひとつ面白さが分からなかったが読み切れているので良いということにする。

use std::collections::VecDeque;

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

fn main() {
    input! {
        n: usize,
        m: usize,
        abc: [(Usize1, Usize1, i64); m],
    };

    let mut edges = vec![vec![]; n];
    for (a_i, b_i, c_i) in abc.iter().copied() {
        edges[a_i].push((b_i, c_i));
        edges[b_i].push((a_i, c_i));
    }

    let mut pos = vec![0_i64; n]; // p_i + x_0
    let mut neg = vec![0_i64; n]; // q_i - x_0
    let mut exists_pos = vec![false; n];
    let mut exists_neg = vec![false; n];

    let mut lbound = 0_i64;
    let mut ubound = 1_i64 << 60;

    let mut deque = VecDeque::new();
    deque.push_back(0);
    exists_pos[0] = true;
    while let Some(u) = deque.pop_front() {
        for (v, c) in edges[u].iter().copied() {
            let mut updated = false;

            if exists_pos[u] && !exists_neg[v] {
                exists_neg[v] = true;
                neg[v] = c - pos[u];
                ubound = ubound.min(c - pos[u]);
                updated = true;
            }

            if exists_neg[u] && !exists_pos[v] {
                exists_pos[v] = true;
                pos[v] = c - neg[u];
                lbound = lbound.max(neg[u] - c);
                updated = true;
            }

            if updated {
                deque.push_back(v);
            }
        }
    }

    if lbound > ubound {
        println!("-1");
        return;
    }

    let mut ans = vec![0_i64; n];

    let mut x = ubound;
    for i in 0..n {
        if exists_pos[i] && exists_neg[i] {
            if (neg[i] - pos[i]) % 2 != 0 {
                println!("-1");
                return;
            }
            x = (neg[i] - pos[i]) / 2;
        }
    }

    for i in 0..n {
        if exists_pos[i] {
            ans[i] = pos[i] + x;
        } else {
            ans[i] = neg[i] - x;
        }

        if ans[i] < 0 {
            println!("-1");
            return;
        }
    }

    for (a_i, b_i, c_i) in abc.iter().copied() {
        if ans[a_i] + ans[b_i] != c_i {
            println!("-1");
            return;
        }
    }

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

今日のコミット。