P - Bridge Elimination Editorial
by 
ebi_fly
この問題は俗に積の和典型と呼ばれる手法で解くことができます。
スコアは、『 \(G\) の各連結成分に含まれる頂点に書かれた整数の和の総積』から『 \(G\) の各連結成分からそれぞれ \(1\) 頂点選び、それらの頂点に書かれた整数の積をとる。それのすべての選び方に対する和』と言い換えることができます。
よって、 \(p(i)\) を『 \(A_1, A_2, \dots, A_N\) の中から \(i\) 個選ぶ全ての場合の値の総積の総和』、 \(q(i)\) を『 \(i\) 個の頂点を選び、 \(G\) の連結成分数が \(i\) の単純連結無向グラフであって、選んだ \(i\) 個の頂点が \(G\) において異なる連結成分にあるような単純連結無向グラフの個数』とすると、問題の答えは
\[ \sum_{i = 1}^{N} p(i) \times q(i) \]
となります。
\(p(i)\) の計算方法
\[p(i) = [x^i]\prod_{j = 1}^N \left(1 + A_j x\right)\]
であるため、 \(O(N^2)\) や \(O(N(\log N)^2)\) などで求めることができます。
\(q(i)\) の計算方法
単純連結無向グラフから橋を取り除いてできた各連結成分は、橋のない単純連結無向グラフ、つまり二重辺連結成分となっています。二重辺連結成分の性質から、単純連結無向グラフの二重辺連結成分を \(1\) 個の頂点に集約して作られるグラフは木となります。
次に以下の問題を考えます。
\(M\) 個の橋のない頂点ラベル付き単純連結無向グラフに対して、辺を \(M-1\) 本追加して連結とするとき、作られるグラフの個数
この問題は、 \(i\) 個目の橋のない頂点ラベル付き単純連結無向グラフの頂点数を \(B_i\) として \(N = \sum_{i = 1}^{M} B_i\) とすると答えは
\[ \left(\prod_{i = 1}^{M} B_i\right) N^{M-2} \]
となります。これは、Prüferコード を用いることで導出することができます。
\(B_i\) を \(i\) 個目のグループの頂点数、 \(r(i)\) は頂点数が \(i\) の橋のない頂点ラベル付き単純連結無向グラフの個数とします。 \(dp[i][j]\) を『 \(i\) 頂点を順序のない空でない \(j\) グループに分け、各グループは橋のない単純連結無向グラフとし、特定の \(j\) 頂点は別々のグループに分かれているとき、各分け方について \(\prod_{k = 1}^{j} B_k r(B_k)\) の和』 とすると \(q(i)\) は
\[ q(i) = dp[N][i] \times N^{i-2} \]
となります。
この動的計画法は以下のような遷移をします。
\[ dp[0][0] = 1 \]
\[ dp[i][j] = \sum_{k = 1}^{i - j + 1} \binom{i-j}{k-1} \times dp[i - k][j - 1] \times k \times r(k) \]
この動的計画法は状態数が \(O(N^2)\) で、遷移が \(O(N)\) であるので \(O(N^3)\) で計算できます。
また、 \(r(i)\) は頂点数 \(i\) の単純連結無向グラフから \(G\) の連結成分数が \(2\) 以上のグラフの個数を引いたものになります。 \(dp2[i][j]\) を『 \(i\) 頂点を順序のない空でない \(j\) グループに分け、各グループは橋のない単純連結無向グラフとしたとき、各分け方について \(\prod_{k = 1}^{j} B_k r(B_k)\) の和』とすると \(dp2\) は以下のように遷移します。
\[ dp2[0][0] = 1 \]
\[ dp2[i][j] = \sum_{k = 1}^{i} \binom{i - 1}{k - 1} \times dp2[i - k][j - 1] \times k \times r(k) \]
よって、 \(r(i)\) は、頂点ラベル付き単純連結無向グラフの個数を \(s(i)\) とすると
\[ r(i) = s(i) - \sum_{j = 2}^{i} dp2[i][j] \times i^{j - 2} \]
となります。 \(dp2\) は \(O(N^3)\) でできるため \(r(i)\) は \(O(N^3)\) で求めることができます。 \(s(i)\) は除原理を用いることで求めることができるため、 \(q(i)\) を \(O(N^3)\) で求めることができました。
まとめ
\(p(i)\) を求めるのに \(O(N^2)\) 、 \(q(i)\) を求めるのに \(O(N^3)\) であるため、全体で \(O(N^3)\) で解くことができます。
posted:
last update: