yukicoder No.753 最強王者決定戦

問題

16人の人間がいる。この16人を一列に並べて順番に組を作ってトーナメントを行ったとき、並べ方に応じて優勝者がただ一人決まる。全てのペアについて、戦ったときどちらが勝つかは決まっている。16!通りの並べ方全てについて優勝者を求めたとき、各人が何回優勝するかを計算せよ。

解法

DPで解く。DPテーブルは以下のようにする。
DP[i][S]: 集合Sの中の人が全員戦った時に人iが優勝する場合の数。ただし、組み方が同じで人の並べ方だけが違うものは同一視する。
(|S|は2べきのみを取り得ることに注意。)
DPの遷移はDP[i][S] <- DP[i][T] * DP[j][S - T] (iがjに勝つ場合)である。

計算量解析はかなり複雑。とりあえずΩ(2^n n^2)とO(4^n n^2)は確定だけどその間が詰められない。

実装上の注意点

16!が64bit整数に収まるか注意する。今回はスターリングの公式から16! ~= (16/e)^16 < 8^16 = 2^48なので問題ない。
同じトーナメントを何回も数えるので、最後に然るべき数を掛けるのを忘れないようにする。(今回は2^15)

提出: #305265 No.753 最強王者決定戦 - yukicoder (Rust)

/// Generates an Iterator over subsets of univ, in the descending order. 
/// Verified by: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3050308
struct SubsetIter { bits: Option<usize>, univ: usize }
impl Iterator for SubsetIter {
    type Item = usize;
    fn next(&mut self) -> Option<usize> {
        match self.bits {
            None => None,
            Some(bits) => {
                let ans = bits;
                self.bits =
                    if bits == 0 { None }
                else { Some((bits - 1) & self.univ) };
                Some(ans)
            }
        }
    }
}
fn subsets(univ: usize) -> SubsetIter {
    SubsetIter { bits: Some(univ), univ }
}

fn solve() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($format:expr) => (write!(out,$format).unwrap());
        ($format:expr, $($args:expr),+) => (write!(out,$format,$($args),*).unwrap())
    }
    let n = 16;
    input! {
        a: [[i32; n]; n]
    }
    let mut a = a;
    for i in 0 .. n {
        for j in i + 1 .. n {
            a[j][i] = -a[i][j];
        }
    }
    let mut dp = vec![vec![0i64; 1 << n]; n];
    for i in 0 .. n {
        dp[i][1usize.wrapping_shl(i as u32)] = 1;
    }
    let mut s = 1;
    while s < n as u32 {
        s *= 2;
        for bits in 0 .. 1usize << n {
            if bits.count_ones() != s { continue; }
            for sub in subsets(bits) {
                if sub.count_ones() != s / 2 { continue; }
                let sub2 = bits - sub;
                for i in 0 .. n {
                    if (sub & 1 << i) == 0 { continue; }
                    for j in 0 .. n {
                        if (sub2 & 1 << j) == 0 { continue; }
                        if a[i][j] == 1 {
                            dp[i][bits] += dp[i][sub] * dp[j][sub2];
                        }
                    }
                }
            }
        }
    }
    for i in 0 .. n {
        puts!("{}\n", dp[i][(1 << n) - 1] << (n - 1));
    }
}

まとめ

なんで入力長を固定にしたり対称行列にしなかったりしたんだ…?