Rustコトハジメ

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

再帰型ビットDP「徒競走」

再帰で解くビットDPの実装演習。 問題によって、ループ(前向き)か再帰(後ろ向き)のどちらが自然かがあるような気がする。この問題は再帰の方が自然。

D - 徒競走

問題

N(16程度)人で徒競走をする、xさんとyさんの順序関係がM個与えられるから、矛盾しない順位の数を計算しなさい。

考え方

順序関係に矛盾しない小さなグループを拡大していく。

実装

fn solve() {
    input! {
        N: usize, M: usize,
        XY: [(usize, usize); M],
    }

    let mut lates = vec![vec![]; N];
    for (x,y) in XY {
        lates[x-1].push(y-1);
    }

    let mut dp = vec![None; 1<<N];
    dp[(1<<N)-1] = Some(1);

    fn rec(s: usize, N: usize, lates: &Vec<Vec<usize>>, dp: &mut Vec<Option<usize>>) -> usize {
        if dp[s].is_some() {
            return dp[s].unwrap()
        }
        let mut res = 0;
        for x in 0..N { // N
            if s & (1<<x) > 0 {
                continue;
            }
            for y in &lates[x] {
                if s & (1<<*y) > 0 {
                    dp[s] = Some(0);
                    return 0
                }
            }
            res += rec(s | (1<<x), N, lates, dp);
        }
        dp[s] = Some(res);
        return res;
    }

    println!("{}", rec(0, N, &lates, &mut dp));
}

考察

とりあえず、ビットDPだと気づくとして、どうやって計算していくのが自然かを考えると、

あるsの値は、そこに何か1つ追加した時の和で表される

とシンプルにいえるので、再帰で実装するべきとなる。

逆に、

www.rustforbeginners.com

巡回セールスマン問題の考え方 - Rustコトハジメ

のような問題は、sが大きいものが、より小さいものによって定義されるため、ループが自然となる。

しかし再帰関数を書くとなると、環境を食べることが出来ないのでrec関数のように、環境を全渡しすることとなる。何か良い方法はないものか。