ARC093 F - Dark Horse

当時E問題と同じセットで出題され、全完が5人しかいなかった。強い人にとっては典型。

  • 例:

F - Dark Horse

問題

2^N人の人がトーナメントで優勝者を決める。各ゲームは基本的に番号の小さい人が勝つが、M人のダークホースがおり、その人は1に勝てる。
人の並べ方(2^N)!通りのうち、1が優勝者になる並び方の総数をmod (10^9 + 7)で求めよ。

解法

1は先頭に固定して良い(あとで場合の数を2^N倍する)。1の対戦に注目すると、最初は1人と、次は2人の中で勝ち上がった者(番号minの者)と、次は4人の中で…最後は2^{N-1}人の中で番号minの者と戦う。これらの中にダークホースがいなければよい。それぞれの人の集合にS_1, ..., S_Nという名前をつける。
包除原理を使うと、集合B \subseteq {1, ..., N}について、i in Bなるi全てについてmin S_iがダークホースであるような人の並べ方の総数が分かれば良いことが分かる。番号の大きいダークホースから見ていき、添字を[最後に加えたダークホースの番号][埋めた集合]とするDPを実行すると、すべてのBに対する値がO(2^N * N * M^2)で計算できる。遷移の係数は以下の命題を使うと計算できる。

1からLまで番号付けされたL個のものがあり、K個の箱がある。i番目の箱にはd_i個のものを入れ、入っているものの番号のminがc_iである必要がある。c_iは昇順に並んでいる。このとき箱へのものの入れ方はC(L - c_K, d_K - 1) * C(L - c{K -1} - d_K, d_{K - 1} - 1) * C(L - c_{K - 2} - d_K - d_{K - 1}, d_{K - 2} - 1) * ...である。

この命題では箱へものを入れる順番の違いは無視されるので、最後に1! * 2! * 4! * ... * (2^{N - 1})!倍する必要がある。

登場する典型

  • 包除原理
  • 「ある箱にはhogehoge番目以降しか入れられない」のような制約がある中での数え上げ
    • ソートして大きい方から見れば正確に計算できる
  • DPの結果使い回し
    • これをしないとO(3^N poly(N, M))くらいになりそう

実装上の注意点

  • あとで数倍する処理を忘れないようにする。
  • DPの遷移で±1などの部分を間違えないようにする(1敗)。
  • 複数の添字があるので、添字の順番を誤らないように注意する(1敗)。
  • 組み合わせの計算を誤らないようにする(1敗)。
  • 数え上げなので、ある程度大きなサンプルが合っていれば安心して良い。

提出: (2019/01/09 22:05 修正, ModIntライブラリの修正により) Submission #3968098 - AtCoder Regular Contest 093 (Rust)

// ModInt省略

fn fact_init(w: usize) -> (Vec<ModInt>, Vec<ModInt>) {
    let mut fac = vec![ModInt::new(1); w];
    let mut invfac = vec![0.into(); w];
    for i in 1 .. w {
        fac[i] = fac[i - 1] * i as i64;
    }
    invfac[w - 1] = fac[w - 1].inv();
    for i in (0 .. w - 1).rev() {
        invfac[i] = invfac[i + 1] * (i as i64 + 1);
    }
    (fac, invfac)
}

fn solve() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($($format:tt)*) => (write!(out,$($format)*).unwrap());
    }
    input! {
        n: usize,
        m: usize,
        a: [usize1; m],
    }
    let (fac, invfac) = fact_init(200100);
    let mut dp = vec![vec![ModInt::new(0); 1 << n]; m + 1];
    dp[m][0] = 1.into();
    for bits in 0 .. 1 << n {
        for i in 0 .. n {
            if (bits & 1 << i) == 0 { continue; }
            for k in 0 .. m {
                let factor = if bits + a[k] <= 1 << n {
                    let x = (1 << n) - bits - a[k];
                    let y = (1 << i) - 1;
                    fac[x + y] * invfac[x] * invfac[y]
                } else {
                    0.into()
                };
                for j in k + 1 .. m + 1 {
                    dp[k][bits] += dp[j][bits ^ 1 << i] * factor;
                }
            }
        }
    }
    let mut inex: ModInt = 0.into();
    for bits in 0 .. 1 << n {
        let mut sum: ModInt = 0.into();
        for i in 0 .. m + 1 {
            sum += dp[i][bits];
        }
        sum *= fac[(1 << n) - 1 - bits];
        for i in 0 .. n {
            if (bits & 1 << i) == 0 {
                sum *= invfac[1 << i];
            }
        }
        if bits.count_ones() % 2 == 1 {
            sum = -sum;
        }
        inex += sum;
    }
    inex *= 1 << n;
    for i in 0 .. n {
        inex *= fac[1 << i];
    }
    puts!("{}\n", inex);
}

まとめ

25分くらいで実装できたのでよかった。達成感を味わえる問題だと思う。