ARC093 F - Dark Horse
当時E問題と同じセットで出題され、全完が5人しかいなかった。強い人にとっては典型。
- 例:
F 程よい典型詰め合わせだと思うんだけどなんでこんなに解かれてないんだろう
— エレベーターに乗ったら行先階ボタンを押す (@DEGwer3456) 2018年3月25日
問題
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分くらいで実装できたのでよかった。達成感を味わえる問題だと思う。