7K12 blog

猫でも分かる何か

ABC210 E - Ring MST

f:id:tkr987:20210813025734p:plain

  •  pA+qB+rC+... \equiv 0 \ (\bmod gcd (A, B, C, ...))

f:id:tkr987:20210813030527p:plain
https://atcoder.jp/contests/abc210/submissions/24941318

最小全域木クラスカル法というアルゴリズムがある。クラスカル法は「全ての頂点が連結になるまでコスト昇順に辺を選択してく」アルゴリズムだが、頂点と辺の数が多いため愚直にクラスカル法は使えない。そこで、クラスカル法を使わずに計算(シミュレーション)で処理する方針を取る。

最も自明なケースとして  N と互いに素な  A_i があった場合  A_i, 2A_i, ..., NA_i (\bmod N) は全て異なる値になるので、その  A_i だけで全て連結になる。そうでないとき、例えば頂点数18で  A_i = 6, 8, 10 を選んだとすると連結成分は2個になるが、これは  gcd(18, 6, 8, 10) と等しい。これは無限長の双六で考えるとサイコロの目が6と8と10だった場合、どれも2の倍数なので無限回数投げると止まるマスは2の倍数なら全て可能性が出てくる、という説明が分かりやすいと思う。一般化すると  A_1, A_2, ... を選ぶと連結成分の個数は  gcd(N, A_1, A_2, ...) ということになる。

上記考察をまとめると以下のような処理で答えが求まる。

クラスカル法の考え方で最小全域木を構築するためコスト昇順にソートし、順番に  A_i を使っていくことにする。このとき  A_i で辺を追加した結果、連結成分の個数が  R_i になったとするとコスト合計は  (R_{i} - R_{i-1}) \times C_i だけ増えることになる( C_i A_i を使って辺を1つ追加したときのコストとする)。連結成分の個数は gcd なので gcd = 1 になるまで繰り返せばコスト合計が求まる。なお  gcd(N, A_1, A_2, ..., A_M) \neq 1 なら連結成分が1個にならないということなので -1 を出力する。

感想: この gcd の性質は初めて知った