N個の集合の合併での最善手 - 早稲田大学チームvivid_turtle 知見共有@ ウィキ

N個の集合を合併して、一つにしたときに、最善の合併手順で行った時に、最終的なベストや経路などを求める問題がある。
例としては、
数字がNこあり、これらのうち二つを選んで差をとり、その差をもともとの数字と置換する。この操作を行えるだけ行うと、数字が一つ残るが、これの最小値を求めよ。
といったりする。

こういう時に、合併するというのは「二つの集合を一つにまとめる」という条件を満たす(そらそうよ)。例えば、足し算、引き算などの演算が条件を満たす。
合併するとき、見た目では集合数が1少なくなってるものの、解法を考える上では、集合数が少なくなったように考えず、合併にあたる演算が適応される範囲が広くなる。と考えるとうまくいきやすい。
演算の中で、複数回重ねたら変化する(引き算ならば、複数回重ねることで+ or -になる)ものは、こういうところで狙われやすい。

diverta2 - C(500)

https://atcoder.jp/contests/diverta2019-2/tasks/diverta2019_2_c

この問題、上記の条件にぴったり当てはまる。
考え方としては、単位集合が併合されて減ったとは考えずに、合併という操作によって影響される単位集合の数が、増えていくと考えたほうがいい。

つまり(合併操作を行うところを[]でかこった)

[{a}, {b}], {c}, {d}, {e}
↓
{a, b}, {c}, [{d}, {e}]
↓
{a, b}, [[c}, {d, e}]
↓
[{a, b}, {c, d, e}]
↓
{a, b, c, d, e}

となる。

この問題では合併操作の第二引数にかかった回数がその単位集合(つまりこの問題では入力で与えられた数列の要素)の正負を決定するのである。
一部の例外はあるものの(全部正、全部負とか)
ここまでくると、負の数には奇数回の演算、正の数には偶数回の演算がかかるように併合すればいいとわかる。
そして、全部正、全部負以外では、
正の数を１つ除き(除いたのをAとする)、ある負の数Bから引く。これをCとおく。
Aから負の数からBを除いたものをすべて引き、これをDとする。
最後にD-Cをすれば、負の数すべてに1回の演算がかかり(Bは最後のD-Cで、それ以外はDを構成する途中で)、正の数はすべて0or2回の演算がかかる(Aはそもそも引かれてなく、それ以外はCの構築と最後のD-Cで二回)構築が完了する。
最後の構築に関しては、似たやつを纏めて引くという考えで例外に気をつければ解ける。
この問題は、合併操作を複数の単位集合に演算がかかると言い換えれば解けるのである。