Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

【ABC137-E: Coins Respawn】グラフに対して前処理を行う

解けなかった問題だが、明らかに学びが多そうで、解いておきたかったので解いた。

E - Coins Respawn

問題

グラフが与えられる。ノード1からスタートし、各辺を通るごとに設定されたコインをもらえるが、ノードNについた時に通った辺の数*Pを請求される。同じ辺を何度も通るのはありとした場合、最終的に残るコイン枚数の最大値を求めよ。

方針

辺を通ることにP払うとしてよい。c-Pは負値がありえるからbellman fordを使う。

負の無限ループをして最大値なしになる場合を判定したい。これにはbellman fordを使って負ループ検出を出来る。

無限ループがあるとしても、1から出発して無限ループを経由してNに到達する場合にしか興味がなく、例えば、サンプル3のように、1から到達出来ない無限ループやNに到達出来ない無限ループがある場合は排除して、負ループ判定がこいつらに反応しないようにしたい。

これには、1から到達出来ない点、Nから到達出来ない点を省く前処理で対応出来る。これにはBFSやDFSなどを使うことが出来る。

実装

fn solve() {
    const INF: i64 = 2_000_000_001;
    input! {
        N: usize, M: usize, P: i64,
        ABC: [(usize,usize,i64); M],
    }

    let mut g = vec![vec![]; N];
    for (a,b,c) in ABC.clone() {
        g[a-1].push(b-1);
    }
    let mut used1 = vec![false; N];
    let mut Q = VecDeque::new();
    Q.push_back(0);
    used1[0] = true;
    while !Q.is_empty() {
        let v = Q.pop_front().unwrap();
        for &u in &g[v] {
            if !used1[u] {
                used1[u] = true;
                Q.push_back(u);
            }
        }
    }
    // dbg!(&used1);

    // リンクを逆順につないだグラフに対してBFSして、
    // Nとの接続性を調べる
    let mut g = vec![vec![]; N];
    for (a,b,c) in ABC.clone() {
        g[b-1].push(a-1);
    }
    let mut usedN = vec![false; N];
    let mut Q = VecDeque::new();
    Q.push_back(N-1);
    usedN[N-1] = true;
    while !Q.is_empty() {
        let v = Q.pop_front().unwrap();
        for &u in &g[v] {
            if !usedN[u] {
                usedN[u] = true;
                Q.push_back(u);
            }
        }
    }
    // dbg!(&usedN);

    let mut g = vec![];
    for (a,b,c) in ABC {
        let connected1N = used1[a-1] && used1[b-1] && usedN[a-1] && usedN[b-1];
        if !connected1N {
            continue;
        }
        g.push(Edge {
            from: a-1,
            to: b-1,
            cost: -(c-P),
        });
    }
    if find_negative_loop(N, &g) {
        println!("-1");
        return
    }

    let d = bellman_ford(N, &g, 0);
    let res = d[N-1];
    println!("{}", max(-res, 0));
}
#[derive(Clone)]
struct Edge {
    from: usize,
    to: usize,
    cost: i64, // can be negative
}
fn bellman_ford(n: usize, es: &[Edge], source: usize) -> Vec<i64> {
    const INF: i64 = 2_000_000_001;
    let mut d = vec![INF; n];
    d[source] = 0;
    loop {
        let mut update = false;
        for e in es {
            if d[e.from] != INF && d[e.to] > d[e.from] + e.cost {
                d[e.to] = d[e.from] + e.cost;
                update = true;
            }
        }
        if !update {
            break;
        }
    }
    d
}
fn find_negative_loop(n: usize, es: &[Edge]) -> bool {
    let mut d = vec![0; n];
    for i in 0..n {
        for e in es {
            if d[e.to] > d[e.from] + e.cost {
                d[e.to] = d[e.from] + e.cost;
                if i == n - 1 {
                    return true;
                }
            }
        }
    }
    false
}

考察

bellman fordは全枝に対してぐるぐるまわしで最短を更新していく手法だから、この中に1からの到達可能性は含まれていない。「Nから到達不能な点だけ省けばいいでしょw」はこの理由で成立しない。(ダイクストラは、最短ルートをとっていく手法だから、1からの到達可能性も考慮される。実際に到達不能なやつは距離無限になる)

到達可能性を調べる時は、BFSの方がコードが楽。今にして思うと、自分でコードを書かずとも01BFSのライブラリを使っても良かったのかなと思う。(到達不能 = 距離無限なので)まぁ微妙なラインか。

意味ない点や辺を前処理で削除するというのはたまにあるらしい。

これとほぼ同じじゃんという指摘がチャットでされていた。

D - Score Attack

上位陣でもふつうのABC-Eに比べると、苦戦してる人が多かったように思う。

グラフアルゴリズムの正しい理解が求められるという意味では、他にもKraskalが時々出ると思うので、きちんと理解しておきたい。