解説AC
web解説を見てよくわからなかったので、自分なりに証明してみました。
素人なので、間違っていたらすみません。
森と、森の各連結成分について、他の連結成分と連結しなければならない次数の不足数
が与えられる(以下、不足数と表現します。)。これを満たすように連結させ、森を1つの木とすることを考えます。
のときは既に木が構成されているので、
を仮定します。
これを達成するための必要十分条件は、連結成分数を、与えられた不足数の合計を
として、
かつ
が成り立つことである。 また、これを満たす時、その構成方法は、
なら、少なくとも一方が不足数2以上である連結成分を選び、連結する
なら、不足数が1である2つの連結成分を連結にする
ことである。
まず、木を構成する上で、なぜ
かつ
という条件が出てくるのかメモしておきます。
木の構成可能条件が出てくる理由
木の辺を1本ずつ切断していくことを考える。
任意の辺を1本切断した時、連結成分数はの2個になり、不足数は
で合計は2となる。
これは、
かつ
を満たす。
次に、本目の切断時に
かつ
が成り立っていると仮定し、
本目の辺を切断した時を考える。
辺が1本以上存在する任意の連結成分の辺を切断し、
に分割されたとする。
には次数の不足が+1ずつされることから
が成り立つ。
本目の辺を切断した後の連結成分数を
、不足数の合計を
とすると、連結成分数は1つ増え、次数の不足は2つ増える。
本目切断時の
から、
、
となるので、
に代入すると、
となる。
従って、が成り立つ。
以上から、木から任意の辺を1本以上取り除くと、かつ
が常に成り立つことが示された。
このようにして条件が出てきます。
次に、かつ
ならば、木が構成できることを構成方法の正当性とともに示します。
かつ
木を構成できる
である間、先程示した帰納法の逆を考えると、任意の連結成分を連結しても常に、
が成り立つ。
連結する2つの連結成分の内、少なくとも一方について、連結前の不足数が2以上であれば、不足数が各々1減っても新たにできる連結成分の不足数は0とならないので、も保たれる。
よって、となるまで、この操作を繰り返す。
となったとき、
かつ
が成り立っていることから、2つの連結成分のそれぞれの不足数が1である。これを連結させることで1つの木とできる。
以上で証明は終了ですが、以下を示しておきます。
補足
であり、
かつ
ならば、
しか存在しない
しか存在しない
ことがあり得ないことを示す。
これが示されると、各段階で常に不足数が2以上の連結成分と1の連結成分が1個以上存在することになる。
また、これが成り立たないと、構成の途中で木にできない状態を作り出してしまうことになる。
しか存在しない状態にならない
この状態になったと仮定すると、となり、
が成立していることから、
が成り立つはずである。
しかし、
という仮定からこれは成り立たない。
しか存在しない状態にならない
となるが、
と矛盾する。
最後に、十分性を示しておきます。
木を構成できるかつ
対偶
であるか、または、不足数0となる連結成分が1つでも存在するなら木を構成できない
を示す。
不足数0である連結成分が1つでも存在すると、その連結成分を連結できないため、1つの木とならない。よって、木を構成できない。
回目の連結操作の終了時点で、
が成立し、
回目の連結操作で
にできると仮定する。
しかし、先程示した帰納法と同様の議論で、回目に
が成立する場合、
回目の操作終了時点に
が成り立つことが証明できる。
よって、仮定と矛盾するため、から
が成立する状態にできない。
従って、の状態から1つの木を構成することはできない。
以上で対偶が示された。
解法
これでweb解説の2つの構成方法
がそれぞれ正しいことがわかりました。
ところで、次の構成方法も問題ないはずです。
この解法でACできました。
(として不足数最大を取らなくても不足数2以上であれば何でも良さそうです)
なお、構成前の前提として、以下の場合も解なしです。
余談ですが、解説にあるような、個数の小さい方から大きい方にマージすることをマージテクと呼ぶのを初めて知りました。