ABC152 - F - Tree and Constraints - Senの競技プログラミング備忘録

概要

サイズNの木が与えられる。それぞれの辺に黒、白の二色のいずれかで塗る。
次のM個の条件をすべて満たす塗り方の場合の数を求めよ。
・頂点u~頂点vを結ぶ経路の上に、必ず1つ以上の白く塗られた辺が存在する。

制約: 1 <= N <= 50, 1 <= M <= min(20, (N-1)*N/2)

ACするまで

1. 少なくとも1つは余事象で考える。
2. 今回は不定数個の満たすべき条件があるため、余事象を拡張した、包除原理を使う。
3. 包除の計算量は、条件を纏められない場合はO(2^M)。条件の組ごとにかける計算量を考える。
4. それぞれの条件となる辺の集合を前もって計算し、条件の組ごとに、愚直にそれぞれの条件に相当する辺の集合を併合する。これは条件の組ごとにO(N^2)。全体では(N*M2^M)で2.5*20^8となり、怪しい。
5. 集合の併合でよく使われるテクニック、bitsetを使うと、最大で64倍の定数倍高速化をかけることができる。
6. AC!

考察

数え上げ問題の「1つ以上〇〇」はつぎのようなものが多い。

Point
「1つ以上〇〇」は、「全部」引く「何一つ○○でない」と等しい。
この条件が複数個あるときは、ベン図の要領でうまく足し引きをすれば求まる。(包除原理)
条件がM個存在するとき、計算量はO(2^m)。ただし、条件をまとめられるなら、O(m)になるときもある。

包除原理に関しては、tsutaj(@tsutaj)さんのスライドが詳しい。
http://compro.tsutajiro.com/archive/181015_incexc.pdf

この問題はこのように考えてみると、いくつか条件だけは満たさず、それ以外はどうでもよいときの場合の数をどうにかして計算できれば良い。

さて、今回の場合満たすべき条件は、

uとvの経路上の辺が、最低1つは黒く塗られてる。

であり、これの逆の条件は、

uとvの経路上の辺が、すべて白で塗られてる。

であるため、いくつかの条件だけ満たさないは、

選ばれた(満たさないと決めた)条件たちの、両端を結ぶ経路に入ってる辺が、すべて白で塗られてる。

この時、白で塗らないといけない辺以外は任意に塗ってよいので、白で塗る必要のある辺の数だけ数えれば、その場合の数は2^(すべての辺の数-白で塗る必要のある辺の数)となる。

さて、これを愚直に考えると、1つの条件の使われる辺はO(N)、条件の個数はO(M)なので、包除原理の部分も合わせると計算量はO(N*M*2^M)となり、これは20 * 50 * 10^6程度なので、10^10となり怪しい計算量となる。

ところで、集合演算に対してbit演算は実装上便利であると知られているが(bitDPなどの例)、具体的にはつぎのようなメリットがある。

Point
整数型を用意して、二進数でいうと2^xの桁が1であるのを「○○がある」、0であるのを「○○がない」として集合を保持するとき。
1. 集合SとTの和集合は、"S | T"。積集合は"S & T"、補集合は"~S"と簡単に書ける。
2. 和集合と積集合を計算する際、整数型としてbit演算をするため、bitで保持しない場合に比べて(bool配列で保持する場合など)最大で64倍の高速化ができる。(64倍は、bool 64個の配列をlong long1つで賄えるため)

このテクニックは、bool値でDPをする場合でも知られている。

これを使うと、数十倍の定数倍高速化が見込めるため、時間内に間に合う。

ACソースコード：
Submission #9823137 - AtCoder Beginner Contest 152

一言

春、頑張るぞ。