ABC210 E Ring MST
まず, $ (i, x)が同じ操作を2回以上行うことは明らかに無駄であるので, 各操作を$ 1回までしか行えないとして考える. ここで, 今考えられるすべての操作を行った時のグラフを考える. すると, できたグラフから辺を選んで連結にする最小全域木(MST)を求める問題に帰着される.
MSTを求めるアルゴリズムとしては, クラスカル法が有名である. クラスカル法とは, 辺をコストの小さい順に試し, 端点の連結成分同士がすでに連結でないならば辺を追加するという貪欲法である. 今回はこの手法を直接用いると間に合わないが, 同じような貪欲アルゴリズムで解くことができる.
クラスカル法の理論を利用すると, 操作は$ C_iの昇順に行い, 辺を追加できるだけ追加していくのが最適であるということがわかる. よって, あとは各操作について, 辺を最大で何本追加することができるか求めればよいことになる.
ここで, グラフの連結成分の個数に注目すると, 余計な辺を追加しないことを考えると, (連結成分の個数の変化量) = (辺の追加量)となっていることがわかる. よって, 各状態でのグラフの連結成分の個数が分かればよい. 実はこれは$ gcd(N, A_1, A_2, ..., A_i)となっていることが示せる.
よって貪欲法を用いることで, この問題を$ O(M (\log N + \log M))で解くことができた.