ABC195 F – Coprime Present 別解解説

問題

パナソニックプログラミングコンテスト(AtCoder Beginner Contest 195)F – Coprime Present
問題リンク:https://atcoder.jp/contests/abc195/tasks/abc195_f

解説

注意:一部で僕の思考過程を再現しながら解説します。最短ルートとは限りません。

利用する典型テクニック

  • 半分全列挙 → bit DP

前置き

$N$ をカードの枚数 $B-A+1$とします。問題の制約から $N \le 73$ です。

$O(n2^{n/2})$ 時間で独立集合の数え上げ

カードが $40$ 枚程度なら、独立集合の数え上げで解ける。

 カードを頂点、数字が互いに素でないカードの組を辺とすれば、独立集合の数を求める問題になります。この問題は、下の方法(後で使います)で $n$ 頂点に対して計算量 $O(n2^{n/2})$ で解けますが、今のままでは $n \le 73$ なので無理です。

  1. 頂点の隣接関係を $n$ 個のビット配列して持つ
  2. 頂点集合を $S_0$ と $S_1$ の $2$ つに分ける
  3. $S_0$ と $S_1$ それぞれについて、 bit DP で各部分集合 $s$ が独立集合かどうか求める
  4. $S_1$ での 2. の結果をうまく累積和(高速ゼータ変換)して、各部分集合 $s$ について $s$ の部分集合のうち独立集合であるものの個数を求める
  5. $S_0$ の各部分集合 $s$ について、 $s$ のどの頂点とも隣接しない $S_1$ の頂点の集合 $s_1$ として $s_1$ における 3. の結果を求め、足し合わせる

偶数を特殊扱い

奇数すべてと偶数高々 $1$ つの場合(高々 $39$ パターン)について求まればよい。

 偶数は複数選べません。これが求まれば、「偶数を含まない場合」と「特定の偶数を含む場合」が求まり、足し合わせれば答えになります。

 計算量は、各パターンで $O(N2^{N/4})$ 、パターン数 $O(N)$ なので全体で $O(N^22^{N/4})$ ですが、TLE します(しました)。

提出コード(TLE):https://atcoder.jp/contests/abc195/submissions/20896332

計算結果の使いまわし

偶数を含まない場合の結果を繰り返し用いて、全体で $O(N2^{N/4})$ 時間で求められる。

 各パターンで計算内容はほぼ変わりません。「特定の偶数 $x$ を含む場合」は、「偶数を含まない場合」のうち、 $x$ と隣接するものを含まないものの個数です。「偶数を含まない場合」の結果を使って次のように $O(2^{N/4})$ 時間で求められます。

  1. 前計算として、 $S_0$ の各部分集合 $s$ について、 $s$ のどの頂点とも隣接しない $S_1$ の頂点の集合を $s_1(s)$ として保存しておく
  2. $S_0$ の各部分集合 $s$ で $x$ と隣接する頂点を含まないものについて、 $x$ と全く隣接しない $s_1(s)$ の頂点の集合を $s_1$ として $s_1$ における 3. の結果を求め、足し合わせる

提出コード

コンテスト後の提出:https://atcoder.jp/contests/abc195/submissions/20897771 https://atcoder.jp/contests/abc195/submissions/20927992 (4 月 24 日 訂正、リンク先は同じです )
計算量は前述の通り、 $O(N2^{N/4})$ です。

コンテスト中の提出:https://atcoder.jp/contests/abc195/submissions/20897771
計算量は定数倍が小さめの $O(N^22^{N/4})$ です。

タイトルとURLをコピーしました