physics0523's 精進ログ

主に競プロの面白い問題の解法をメモします

Double Clique (NAIPC2018-B)

https://www.acmicpc.net/problem/16041

$N$ 頂点 $M $ 辺のグラフ $G$ が与えられる。

頂点の部分集合 $S$ であって以下の条件を満たすものを $\mod 10^9+7$ で求めよ。

  • $S$ から誘導される部分グラフは完全グラフである。
  • 頂点全体の集合を $V$ としたとき、 $V \setminus S$ から誘導されるグラフに辺はない(補グラフが完全グラフである)。

$1 \le N,M \le 2 \times 10^5$

 

まず、 $\mod 10^9+7$ はこけおどし。実は $O(N)$ 個しかない。(自分が公式の実装例を読解している時、これを知ってもあまり方針がピンと来ませんでしたが…)

ここで、ある $S$ の取り方を吟味しよう。

実は、次の事柄が成り立つ。

  • ある valid な取り方で $|S|=k$ となったとき、 valid な取り方でありうる $|S|$ は $k- 1,k,k+1$ のみである。

証明:

今の $S$ から $2$ 頂点以上を $V \setminus S$ 側に動かすことは許されない。逆に、今の $V \setminus S$ から $2$ 頂点以上を $S$ 側に動かすことも許されない。

ここから、 valid な取り方として考えられるサイズは高々 $2$ つの連続する整数であるということも言える。 

 

さらに、常に次の事柄も成り立つ。

  • $S$ 中の頂点 $u$ 、 $V \setminus S$ 中の頂点 $v$ を好きに選ぶ。
  • この時、 $u,v$ をどう選んでも ( $u$ の次数 ) $\ge$ ( $v$ の次数 ) が成り立つ。

証明:

まず、 ( $u$ の次数 ) $\ge |S|-1$ 、 ( $v$ の次数 ) $\le |S|$ である。

これは、「 $u$ から $S$ 中の他の頂点全てに辺が伸びている必要がある」「 $v$ から辺が伸びて良いのは $S$ 中の頂点のみである」ことから言える。

ここで、 ( $u$ の次数 ) $= |S|-1$ 、 ( $v$ の次数 ) $= |S|$ なるケースがあるとマズい。このような場合 $v$ から $S$ 中の全てに辺が伸びている必要がある。しかし、 ( $u$ の次数 ) は $|S|-1$ であるので $S$ に含まれない頂点に辺を伸ばす余裕はない。よって、このようなことは起きないことが言えた。

 

次に、この等号成立条件を吟味する。

等号が成立する場合、先ほどの 頂点 $v$ から少なくとも $|S|-1$ 辺の辺が伸びている必要がある。これを以下の $2$ 通りに場合分けする。

  • $v$ から丁度 $|S|$ 辺伸びている場合
    • $S$ に $v$ を付け加えても valid な取り方である。
  • $v$ から丁度 $|S|-1$ 辺伸びている場合
    • $v$ から辺が伸びていない頂点 $w$ が $S$ 中にただ一つ存在する。このとき、 $v$ と $w$ を入れ替えても、 $v$ を取り除いても valid な取り方である。
    • このとき、 $S$ 中の $w$ 以外の頂点は次数が $|S|-1$ より真に大きいことに注意されたい。

ここで、各頂点の次数により着目すると、どちらの場合でも以下が成立する。

  • valid な取り方がある時、元のグラフ $G$ について、ある閾値 $k$ が存在して次数が $k$ 以上の頂点から誘導されるグラフが完全グラフである。

更に、等号が成立していない場合でもこれは成立し、ある $k$ でこれが成り立ったなら全ての整数 $l \ge k$ についてもこれは成立する( 着目する頂点が部分集合になるので )。

 

これを使って、以下を満たす最小の $k$ を探索する。

  • 次数 $k$ 以上の頂点のみに着目した場合、それらから誘導される部分グラフが完全グラフである。

つまり、 $S$ 側たりうる頂点をなるべく大きく取った場合 ( $V \setminus S$ をなるべく小さく取った場合 ) に対応する。

この場合で invalid であるとは何を意味するか考える。

  • 取り方のおかげで、 $S$ 側は完全グラフであるのでこちら側の条件は無視して良い
  • よって、 $V \setminus S$ に辺が存在することになる

$V \setminus S$ 側の条件は $k$ を増やすにつれ真に厳しくなる(存在しないべき辺が増えていく)ので、これで invalid なら絶対に無理。

逆に、これで valid な $S$ が発見された場合に解の数を数え上げる。

まず $S$ そのものの $1$ 通りに加えて、 $S$ 側について頂点を「ひとつ追加」・「ひとつ入れ替え」・「ひとつ削除」した場合を考える。先ほどの議論よりこれだけ考えれば十分である。

  • $S$ に含まれないかつ $S$ の全てに接続された頂点があれば、その頂点を追加することが許される。
  • $S$ に含まれるかつ $S$ 以外に辺が全く伸びていない頂点があれば、その頂点を削除することが許される。

実は、ひとつ入れ替えについては考えなくてよい。

証明:

  • $S$ の取り方より、 ( $S$ に含まれる頂点の次数 ) $>$ ( $V \setminus S$ に含まれる頂点の次数 ) が言える。等号が含まれないことに注意。
  • この状況下で頂点を入れ替えてしまうと、 $S$ 側の頂点 $u$ と $V \setminus S$ に含まれる頂点 $v$ であって ( $u$ の次数 ) $<$ ( $v$ の次数 ) なるものが存在してしまうため、不正である。

この一連の流れを実装することで、この問題に正解できる。

 

https://ideone.com/Xb0HFN

次数をうまく使ったトリックのような問題。想定解を読解してこの証明まで辿り着いたが、こんなのどうやったら自力で思いつけるんだ…