AtCoder Regular Contest 099 E - Independence

お題箱より。

解説

問題文をグラフ理論の言葉で解釈します。 $N$ 個の頂点を2つの集合 $X, Y$ に分け、それぞれの集合内では任意の2頂点間に辺が存在している（すなわち、クリークになっている）必要があります。 $X, Y$ の頂点数をそれぞれ $x, y$ とすると、最小化したい値は $\frac{x(x-1)}{2} + \frac{y(y-1)}{2}$ です。そして $y=N-x$ なので、集合 $X$ のサイズ $x$ だけを考慮すれば良いことが分かります。

クリークの問題では「補グラフ」、すなわち任意の2頂点間の辺の有無を反転させたグラフを考えるとうまくいくことがあります。補グラフを取るとクリークは独立集合に、すなわち「任意の2頂点間に辺が存在している」は「どの2頂点間にも辺が存在していない」となります。頂点が2つの集合 $X, Y$ に分けられ、それぞれの集合内ではどの2頂点間にも辺が存在していない…これはまさに二部グラフです。

f:id:betrue12:20210202201636p:plain

与えられたグラフの補グラフを取り、これが二部グラフとなるように頂点を2つの独立集合 $X, Y$ に分けることを考えます。このとき頂点の割り振り方は連結成分ごとに決めることができて、

まずその連結成分が二部グラフになっているかを確認する。そうでなければ題意を満たすことは不可能。
連結な二部グラフであれば2つの独立集合への分け方は一意なので、そのうちどちらを $X$ に割り振るかを決める。

という手順を全ての連結成分について行うことで頂点を割り振ることができます。

冒頭で確認したように、答えを求めるには割り振った後の集合 $X$ のサイズ $x$ としてどの値を実現できるかが分かれば十分です。各連結成分における2つの独立集合のサイズのうちどちらか一方を $x$ に加算していったときの総和としてあり得るものを列挙したいので、これは部分和問題と同様の動的計画法を用いて解くことができます。