[AtCoder] ABC152 F – Tree and Constraints (600点)

2020年1月25日AtCoderbit演算, bit全探索, 包除原理, , 余事象, 制約, 600点

問題へのリンク

問題概要

N頂点の木がある。辺を白か黒で塗るとき、以下のような制約をM個満たすような塗り方は何通りか?

制約 i:頂点 \(u_i\) と頂点 \(v_i\) を繋ぐパス上に、黒く塗られた辺が1つ以上存在する

制約

\begin{align}
&2 \leq N \leq 50 \\
&1 \leq M \leq min(20, N(N-1)/2)
\end{align}

考え方

「黒く塗られた辺が1つ以上」という条件のままでは、どのように考えていいか良くわかりません。「〜1つ以上」と言われたときは、その余事象を考えると条件がシンプルになることが多いです。

よって余事象を考えると問題は以下のように言い換えられます。

以下のようなM個の条件を1つも満たさない塗り方は何通りか?
¬制約 i:頂点 \(u_i\) と頂点 \(v_i\) を繋ぐパス上は全て白である

白になる辺の数が C 個と分かっていたら、他の辺の塗り方は自由なので \(2^{N – 1 – C}\)通りと簡単に求めることが可能です。

全体を辺の塗り方2^Nとしたときの、ベン図の外側の部分が答え

ベン図で考えると、全ての円の外側の部分(全体 – 余事象)が答えになります。このような状況では、余事象の部分(円の内側の範囲全て)が何通りかを求めるのに「包除原理」と呼ばれるものを使うことができます。

¬制約 をいくつか選んで、選んだ ¬制約 を全てを満たすときの塗り方を数えるとします。選んだ ¬制約 の数を k とすると、

  • k が偶数ならその部分を足す
  • k が奇数ならその部分を引く

ということをすると、最終的に「全体 – 余事象」を求めることができます(0の時は全体)。制約が2つや3つの場合で確かめてみてください。

¬制約 の選び方は\(2^M\)通りあるので、1つずつ計算すれば時間内に計算が可能です。

解き方

大まかな手順は以下の通りです。

  1. 制約ごとに、頂点 \(u_i\) と頂点 \(v_i\) を繋ぐパス上の辺を求めておく
  2. 包除原理によって、\(2^M\)通りの計算を行い、「全体 – 余事象」を求める

まずは制約ごとに、白くなるべき辺の場所を求めておきます。求め方はいくつかありますが、深さ優先探索で求める方法や、LCA(最近共通祖先)を使って求める方法などがあります。後で計算しやすくするために bit で管理しておくと良いです(白くなる辺のbit を立てておくなど)。

そして、包除原理で計算を行えば良いです。¬制約 の選び方は bit全探索によって全ての選び方を列挙することができます(bit が立っているとき、その制約を選ぶことにするなど)。

白くなる辺の管理に bit を使い、包除原理でも bit全探索を行うので、bit の扱いに慣れていないと難しく感じるでしょう。

解答例

深さ優先探索を用いた例

公式の解説とは違いますが、LCAのライブラリを作っていない人はこちらのほうが簡単です。

LCAを用いた例

LCAを用いると、2頂点間の距離を\(O(logN)\)で求めることができます。これにより、2頂点を繋ぐパス上にある点 a が存在するかどうかも\(O(logN)\)で求めることができます。

パス上に辺が存在するかは、パス上に辺の両端が存在することと同値です。