ABC152-F Tree and ConstraintsをbitDPで解く

ABC152-F "Tree and Constraints"の解説記事です。想定解法やいくつかある解説記事はどれも包除原理を用いた解法でbitDPでの解説記事が見つからなかったので、簡単に書き残しておきます。

問題へのリンクはこちら

辺を順番に塗り分けていきます。

最初の段階ではM個の制約はどれも満たされていません。辺を黒く塗ったとき、いくつかの制約が満たされることがあります。

ある時点である制約が満たされているとき、その後どのような塗り分け方をしてもその制約が再び満たされなくなることはありません。

なので、N-1本の辺を塗り分け終えるまでに、すべての制約を1度でも満たせばよいです。

制約（紛らわしいですが、ここでいう制約は入力される値の範囲です）をぐっと睨むとMが非常に小さいのでbitで管理したい気持ちになります。

　dp[i][S]:=i個目の辺を塗り終えた時、状態Sとなっている塗り分け方の数

と定義します。

ここでSは、既に満たしている制約の集合です。これをbitで管理します。j番目のbitが立っている(1になっている)とき、j番目の制約が既に満たされていることを意味します。10進数整数で表すと0≦S<2^Mとなります。

初期値はdp[0][0]=1となりますね。

この配列を配るdpで更新していきます。

　dp[i+1][S] += dp[i][S]

これはわかりやすいですね。辺を白く塗ったときに制約が新しく満たされることはないためです。

i本目の辺を黒く塗るとき、状態がどのように変化するかを考えます。

ある制約jについて

ということが言えます。

集合Tを、i本目の辺が2点(uj,vj)のパスの一部であるような制約jの集合とします。

TをSと同じようにbitで管理しておくことで、次の式が成り立ちます。

　dp[i+1][S | T] += dp[i][S]

集合Tは、制約jで与えられる2点(uj,vj)のパス上にある点を事前に計算しておくことでO(M)で求められます。この事前計算はLCAを使うと楽にできますが、今回の問題は小さな木なので、すべての制約に対してBFSと経路復元を行っても十分間に合います。

あとはいつも通りfor文でDPやるだけです。

dp[N-1][(1<<M)-1]が求める答えとなります。答えが32bitに収まらない可能性があるので、64bit型整数を使うのがよいでしょう。

計算量はO(N*(2^M))となります。

普通にACした時の乱雑コードですが、一応自分の提出を置いておきます。（C#です）

包除原理解法もやらなきゃな～

G4NP0Nのブログ