競プロ典型90問 049 Flip Digit 2(★6)
長さ$ N + 2のビット列$ S'を考える. ここで, $ S'において, $ d_i := $ S'_iと$ S'_{i + 1}が等しいか? という長さ$ N + 1の配列$ dを定義する. すると, 操作は$ d_{l_i - 1}と$ d_{r_i}を反転させるという操作に言い換えられる. このように, 区間を反転させる問題について, 隣り合う要素の差分をとるのは典型的な考察テクニックである. この問題では, ここからさらに変形し, グラフに帰着する. $ N + 1頂点の, $ l_iから$ r_iへコスト$ C_iのグラフを張った$ M辺のグラフを考え, 最初はすべての頂点に白が塗られているとする. すると, 操作は辺でつながる$ 2頂点$ l_i, r_iについて, それぞれの色を白なら黒に, 黒なら白に反転させるという形に言い換えられる. ここで小さいケースについて実験してみると, $ 2^{N + 1}通りの塗り方のうち, $ 2^N通りの色の塗り方が実現されればよいということが分かる.
ここで, $ 2^N通りの色が実現できるという条件は, グラフが連結であるということが必要十分条件である. なぜなら, グラフが連結ならば全域木が作れるので, ある全域木をとってくると, 根以外の色については葉から順に決めていくことで自由に決められるからである. よって, コストが最小の全域木をとってくればよく, これは最小全域木問題そのものである.
ゆえに条件を言い換えることにより, この問題を$ O(M \log N)で解くことができた.