2020年6月15日月曜日

CodeChef June Challenge 2020 - Convenient Airports

辺をつなぎかえて2つの連結成分を1つの連結成分にするとき、サイクルをつぶしながらつなげばノーコストでつなげるので、連結成分ごとにサイクルの数のようなものを数えたい気持ちになる。何を数えるのか突き詰めると、結局「木と比べた時の余剰辺の数」を数えればいいことがわかる。

$K$個の連結成分のサイズを$n_1, ..., n_K$、辺数を$m_1, ..., m_K$とするとき、$m_1-n_1+1, ..., m_K-n_K+1$がそれぞれの余剰辺の数にあたる。連結成分が余剰辺の数に関して降順にならんでいるとする。これらを先頭から連結させていくとき、連結後の余剰辺は$\sum m_i - \sum n_i + 1$個であり、これが0になるまではノーコストで連結できる。余剰辺が0になるのは残っている連結成分がすべて木になる時で、以降は木同士をコスト2でつないでいく必要がある。

ただし、孤立点は(余剰辺のある連結成分に対してもノーコストでつなげないので)特別に扱う必要がある:

  • 連結成分$C$に余剰辺が1つあると、2つの孤立点をコスト2で$C$につなぐことができる。
  • 連結成分$C$に余剰辺がない、あるいは孤立点が1つしかない場合は、1つの孤立点をコスト2で$C$につなぐ必要がある。

さて、スコアを求めるだけではなく実際にシミュレーションしなくてはならない。最初にUnion-Findで辺を走査して、連結成分ごとに「ベースとなる木に含まれる辺」と「余剰辺」に分けた上で、余剰辺の数の降順でソートし、それらを(辺を組み替えながら)併合していった。孤立点は最初から分離しておいて、最後に併合した。