CodeForces #485 Div1 C AND Graph

codeforces 競プロ

Um_nik回のCが面白かったので。
あと、自分の解法が想定解と違ったっぽいので。

問題概要

n ビットの二進数 a_i が m 個与えられる。
a_i \& a_j = 0 のとき頂点 i,j に辺を張ったグラフの連結成分数を求めよ。

制約

  • 1 \leq n \leq 22
  • 1 \leq m \leq 2^n
  • 0 \leq a_i \lt 2^n
  • a_i はdistinct

想定解法

writerのeditorial
まず、X\&Y=0 は Y が \sim X に包含されてる（\sim X\&Y=Y）というのと同値です。
m 個の頂点 S_i と、2^n 個の頂点 T_i を用意する。
S はそのまま入力の数に対応する頂点で、T は高速ゼータ変換的な遷移用の頂点。
ここに以下のように有向辺を張っていく。

  • S_i → T_{\sim a_i}
  • j が i のビットを１つ 1 から 0 に置き換えた数であるとき、 T_i → T_j
  • T_{a_i} → S_i

こうすると、S_i ⇒ S_j のパスがあることが a_i\&a_j=0 と同値になる。
そんで、「まだ訪れてない頂点からdfsをして到達可能な頂点をvisitedにする」という操作を行えた回数が連結成分数になる。

この解法のミソは、a_i\&a_j=0 ってのが i,j に対して対称なので、S_i ⇒ S_j のパスがあるなら必ず S_j ⇒ S_i のパスもあるってところ。
普通、有向グラフでDFSしても連結成分数なんて求まらないし、そもそも"連結"の定義がよく分からないんだけど、この性質があることによって S の中での連結成分が無向グラフと同じように定義できてる。
なんていうか、T が無向辺的な役割をしてると考えるといいのかな。

僕はこのへんに気づかなくて有向グラフにしてもしょうがないしな・・・って思ってこの方針を捨ててしまった。

別解 by snuke

まず計算量の悪い解法として、以下のものは思いつきます。

  1. 高速ゼータ変換で dp_i = 「a_j が i に包含されるような j のリスト」を求める。
  2. dp_{\sim a_i} の各要素と i をUnionFindでくっつけて、連結成分数を求める。

ここで、なんとかして dp_i に持たせる値をリストじゃなくて１つの数のみにできないかというモチベーションを得ます。
「dp_{\sim a_i} の各要素と i 」をくっつけるかわりに、「dp_{\sim a_i} の代表１つと i 」と「dp_{\sim a_i} の全要素を互いに」くっつけることにすれば、dp_i には代表１つを記録しておくだけでよくなりそうです。
整理していくと以下のような解法になります。

  1. 前処理として、高速ゼータ変換で E_i = 「i を包含するような \sim a_j が存在するかどうか」を求める。
  2. 高速ゼータ変換で dp_i = 「a_j が i に包含されるような j の代表（例えばmaxなど）」を求める。
    • ただし、E_i = false の場所は dp_i = -1
    • 高速ゼータ変換中に２つの頂点 u,v をマージしたくなった場合は、u,v をUnionFindでくっつけたのち代表のみを残す
      • （E_i = true ということは、なんらかの頂点 w が存在して、u-w と v-w の２つの辺が張られるはずなので u-v は同じ連結成分になる）
  3. dp_{\sim a_i} と i をUnionFindでくっつけて、連結成分数を求める。

まとめ

どちらの方針の方が思いつきやすいのかはよくわかりませんが、どちらにせよ面白い発想が必要とされる良問だと思いました。

ちなみにセットとしては、LGM writerにしてはEFが簡単、というかC~Fに難易度差があまりないように感じたが、終盤ジャッジがつまったりDで苦しむ人が多かったりで４完すらそれほど多くなかったらしい。
他の問題もD以外は普通に面白い回だったと思う。Dもこういうのはサラッと通せるようにしとかないとね。