コンテストでの時間切れや解けなかった過去問を振り返って供養していく
問題
Difficulty: 1895 (記事作成時点)
供養
解法
- グラフの頂点集合 $V$ の部分集合 $S$ および $S$ からなる $G$ の誘導部分グラフ $G(S)$ についてこの問題を解いた場合の解を $\mathit{DP}_{S}$ とすると、$\mathit{DP}_{S}$ は下記のように求められる
\begin{align}
\mathit{DP}_{S} =
\begin{cases}
1 & (G(S) \text{がクリーク}) \\
\mathrm{min}_{T \subset S} \left( \mathit{DP}_{T} + \mathit{DP}_{S \setminus T} \right) & (\text{それ以外})
\end{cases}
\end{align}
- $S$ の部分集合の列挙を高速化するために、$N$ bitの整数を使う
- $u \in S$ である $u$ に対応するbitを立てた整数を $n$、$m = (n - 1)\; \mathrm{AND}\; n$ とする
- $m = 0$ となるまで $m = (m - 1)\; \mathrm{AND}\; n$ としていき、その過程で出てくる $m $ に対応する集合が $S$ の部分集合となる
- $\mathit{DP}_{V}$ が答えとなる
実装
計算量は誘導部分グラフがクリークであることの判定が部分集合全体で $O(N2^{N})$、部分集合の列挙について、グラフの各点を $T, S \setminus T, V \setminus S$ に分類することに等しいので $O(3^{N})$、全体で $O(3^{N})$
公式解説
躓いた点
