競プロ典型049 - salpikのブログ

問題

atcoder.jp

考察過程

この問題は $\mathbb{R}^{N}$ のベクトル空間を張れるようなベクトルを基底を選ぶことに相当している。
一般に $\mathbb{R}^{N}$ のベクトルを表現するには $N$ 個の成分で表現する必要があるが、今回の問題では少し考え方を変えて、隣同士の値に変化があるかという情報をノードにして0/1で表現することにする。すると、各商品についてLとRの部分だけがビットの変わり目となるのでそこのノードのみを1とするような状態として保持しておけば情報として十分である。なお便宜上ベクトル空間の両端に0の成分があることにする。
ある商品のbit情報の表現
そして $2^{N}$ の全てのビットを表現するには、 $N+1$ このノードを全て自由に決定できることが必要十分条件となる。ただし両端のビットは0なので、 $N+1$ このノードの1の数は偶数でないといけない制約条件があり、自由度が1下がり実質の自由度は $N$ となる。
$2^{N}$ のうちのあるbitの表現
それぞれの商品について、1となっている2つのノード間に辺を張ることにする。
互いに行き来できるノードを同じグループと呼ぶことにすると、同じグループにあるノードは商品を選ぶ操作をしても1の数は偶数を保ったままである。
したがって、もし別のグループに存在しているノードAとBがあった場合、ノードAとノードBのみを1にするようなビットは実現できないことがわかる。
この考察から、全てのノードが同じグループでないといけない。
逆に全てのノードがつながっている時、最低 $N$ 本の辺でつながっているので、自由度 $N$ で0/1を表現でき、全てのbitの組み合わせを表現できることになる。
以上の考察からノードが全てつながっていれば $2^{N}$ の全てのビットを表現できると言えるので、最小全域木を求める問題に帰着したことがわかる。