解説AC

web解説を見てよくわからなかったので、自分なりに証明してみました。
素人なので、間違っていたらすみません。

森と、森の各連結成分 $C_i$ について、他の連結成分と連結しなければならない次数の不足数 $D_i$ が与えられる(以下、不足数と表現します。)。これを満たすように連結させ、森を1つの木とすることを考えます。

$C=1$ のときは既に木が構成されているので、 $C\geq 2$ を仮定します。

これを達成するための必要十分条件は、連結成分数を $C$ 、与えられた不足数の合計を $D$ として、

$D=2C-2$ かつ $D_i\gt 0$

が成り立つことである。また、これを満たす時、その構成方法は、

$C\geq 3$ なら、少なくとも一方が不足数2以上である連結成分を選び、連結する
$C=2$ なら、不足数が1である2つの連結成分を連結にする

ことである。

まず、木を構成する上で、なぜ
$C=2C-2$ かつ $D_i\gt0$
という条件が出てくるのかメモしておきます。

木の構成可能条件が出てくる理由

木 $T$ の辺を1本ずつ切断していくことを考える。

任意の辺を1本切断した時、連結成分数は $C_1,C_2$ の2個になり、不足数は $D_1 = D_2 = 1$ で合計は2となる。これは、 $D=2C-2$ かつ $D_i\gt 0$ を満たす。

次に、 $k$ 本目の切断時に $D=2C-2$ かつ $D_i\gt 0$ が成り立っていると仮定し、 $k+1$ 本目の辺を切断した時を考える。
辺が1本以上存在する任意の連結成分 $C_x$ の辺を切断し、 $C_y,C_z$ に分割されたとする。

$C_y,C_z$ には次数の不足が+1ずつされることから $D_y,D_z\geq 1 \gt 0$ が成り立つ。

$k+1$ 本目の辺を切断した後の連結成分数を $C'$ 、不足数の合計を $D'$ とすると、連結成分数は1つ増え、次数の不足は2つ増える。

$k$ 本目切断時の $C,D$ から、 $C' = C + 1$ 、 $D' = D + 2$ となるので、 $D=2C-2$ に代入すると、
$D'-2=2(C'-1)-2\rightarrow D'=2C'-2$
となる。
従って、 $D=2C-2$ が成り立つ。

以上から、木から任意の辺を1本以上取り除くと、 $D=2C-2$ かつ $D_i\gt 0$ が常に成り立つことが示された。

このようにして条件が出てきます。

次に、 $D=2C-2$ かつ $D_i\gt 0$ ならば、木が構成できることを構成方法の正当性とともに示します。

$D=2C-2$ かつ $D_i\gt 0$ $\Rightarrow$ 木を構成できる

$C\geq 3$ である間、先程示した帰納法の逆を考えると、任意の連結成分を連結しても常に、 $D=2C-2$ が成り立つ。

連結する2つの連結成分の内、少なくとも一方について、連結前の不足数が2以上であれば、不足数が各々1減っても新たにできる連結成分の不足数は0とならないので、 $D_i \gt 0$ も保たれる。

よって、 $C=2$ となるまで、この操作を繰り返す。

$C=2$ となったとき、 $D=2C-2$ かつ $D\gt 0$ が成り立っていることから、2つの連結成分のそれぞれの不足数が1である。これを連結させることで1つの木とできる。

以上で証明は終了ですが、以下を示しておきます。

補足

$C\geq 3$ であり、 $D=2C-2$ かつ $D\gt 0$ ならば、

$D_i = 1$ しか存在しない
$D_i\geq 2$ しか存在しない

ことがあり得ないことを示す。
これが示されると、各段階で常に不足数が2以上の連結成分と1の連結成分が1個以上存在することになる。また、これが成り立たないと、構成の途中で木にできない状態を作り出してしまうことになる。

$D_i = 1$ しか存在しない状態にならない

この状態になったと仮定すると、 $D=C$ となり、 $D=2C-2$ が成立していることから、 $C=2C-2\rightarrow C=2$ が成り立つはずである。しかし、 $C\geq 3$ という仮定からこれは成り立たない。

$D_i \geq 2$ しか存在しない状態にならない

$D\geq 2C$ となるが、 $D=2C-2$ と矛盾する。

最後に、十分性を示しておきます。

木を構成できる $\Rightarrow$ $D=2C-2$ かつ $D_i\gt 0$

対偶

$D\neq 2C-2$ であるか、または、不足数0となる連結成分が1つでも存在するなら木を構成できない

を示す。

不足数0である連結成分が1つでも存在すると、その連結成分を連結できないため、1つの木とならない。よって、木を構成できない。

$i$ 回目の連結操作の終了時点で、 $D\neq 2C-2$ が成立し、 $i+1$ 回目の連結操作で $D=2C-2$ にできると仮定する。
しかし、先程示した帰納法と同様の議論で、 $i+1$ 回目に $D=2C-2$ が成立する場合、 $i$ 回目の操作終了時点に $D=2C-2$ が成り立つことが証明できる。
よって、仮定と矛盾するため、 $D\neq 2C-2$ から $D=2C-2$ が成立する状態にできない。
従って、 $D\neq 2C-2$ の状態から1つの木を構成することはできない。

以上で対偶が示された。

解法

これでweb解説の2つの構成方法

不足数2以上と不足数1を連結する
不足数が多い2つを連結する

がそれぞれ正しいことがわかりました。

ところで、次の構成方法も問題ないはずです。

初期状態( $M$ 個の辺を繋げた状態)において、不足数が最大のものを $C_x$ とおく。まず、不足数が2以上の連結成分を全て $C_x$ に連結させる。その後、不足数が1の連結成分を $C_x$ に連結させる。

この解法でACできました。
( $C_x$ として不足数最大を取らなくても不足数2以上であれば何でも良さそうです)

なお、構成前の前提として、以下の場合も解なしです。

頂点数と不足数の和が $D=2N-2$ を満たさない
$M$ 個の辺を繋いだ時に不足数が負となる連結成分が存在する

余談ですが、解説にあるような、個数の小さい方から大きい方にマージすることをマージテクと呼ぶのを初めて知りました。

提出コード

geam1113’s diary

主にAtcoderのコンテストの備忘録を書きます。AtCoder緑と水色を行ったり来たりしています。

ABC239F Construct Highway

木の構成可能条件が出てくる理由

$D=2C-2$ かつ $D_i\gt 0$ $\Rightarrow$ 木を構成できる

補足

$D_i = 1$ しか存在しない状態にならない

$D_i \geq 2$ しか存在しない状態にならない

木を構成できる $\Rightarrow$ $D=2C-2$ かつ $D_i\gt 0$

解法

木の構成可能条件が出てくる理由

かつ木を構成できる

補足

しか存在しない状態にならない

しか存在しない状態にならない

木を構成できるかつ

解法

$D=2C-2$ かつ $D_i\gt 0$ $\Rightarrow$ 木を構成できる

$D_i = 1$ しか存在しない状態にならない

$D_i \geq 2$ しか存在しない状態にならない

木を構成できる $\Rightarrow$ $D=2C-2$ かつ $D_i\gt 0$