E - Ring MST（1610）

問題

問題文

N 個の頂点と 0 本の辺からなる無向グラフがあります。 N 個の頂点をそれぞれ頂点 0、頂点 1、頂点 2、…、頂点 N − 1 と呼びます。
このグラフに対する M 種類の操作を考えます。
i = 1 , 2, … , M について、i 番目の操作は「 0 ≤ x < N を満たす整数 x を選び、頂点 x と頂点 (x+Ai ) mod N を結ぶ無向辺を追加する」という操作です。ただし、a mod b は a を b で割った余りを表します。 i 番目の操作を 1 回行うと Ci 円の費用がかかります。
あなたは、M 種類の操作をそれぞれ好きな回数（ 0 回でもよい）行うことができます。 例えば、3 種類の操作がある場合、1 番目の操作を 2 回、2 番目の操作を 0 回、3 番目の操作を 1 回行うという選択が可能です。グラフを連結にすることが可能かどうかを判定し、可能な場合はそのためにかかる費用の合計として考えられる最小値を求めてください。

制約

2 ≤ N ≤ 10^9
1 ≤ M ≤ 10^5
1 ≤ Ai ≤ N−1
1 ≤ Ci ≤ 10^9
入力はすべて整数

考察

まず、構築できるかどうかを判定したいのでとりあえず全てのコストを１としておきましょう。いきなり一般化して考えるのは大変なので、具体例を考えます。

N = 12, Ai = 2とします。このとき、グラフの辺を張るという操作は、2個隣の数字と手を繋ぐという操作になります。0を始点として手つなぎを開始すると次のようになります。

0-2-4-6-8-10

10の右隣は0なので始点に戻ってきてしまいました。また、同様に1を始点とすると、

1-3-5-7-9-11

となります。これも、11の隣は1ですので始点に戻ってますね。このように各始点に戻るまでどんどん手を繋いで行きます。ここでは一旦、「ループ長は6になる」ということに着目しておきます。ループ長がわかれば単純な割り算で「グループ数」を計算することができます。この考え方をあとで使います。

他の数でもループ長を観察してみましょう。次は3です。

0-3-6-9
1-4-7-10
2-5-8-11

ですね。ループ長は4になります。あと２つやります。７をみてみましょう。

0-7-2-9-4-11-6-1-8-3-10-5

ループ長は12です。これが最長になります。最後に8を見てみます。

0-8-4
1-9-5
2-10-6
3-11-7

ループ長は3ですね。

このループ長は「最小公倍数(lcm)」を用いることで求めることが可能です。図解すると次のようになります。

ここで、ループ長をLとしますと、

L = lcm(N,Ai) / Ai

です。 そしてグループ数 G は

G = N / L

ですので、上の式を代入すれば

G = N / {lcm(N,Ai) / Ai} = N * Ai / lcm(N,Ai)

となります。この式にピンときた方はとても鋭いです。これって「最大公約数:gcd」なんです。gcdとlcmには次のような関係があります。

gcd(a,b) * lcm(a,b) = a*b

両辺をlcmで割ってあげますと、まさしくグループ数Gになります。

長々と説明してきましたが、

グループ数 G はNとAi の gcdで求められる

ということがわかりました。これがわかったことによりグッと答えに近づきました。N 個ある頂点は Ai によって、gcd(N, Ai)個のグループにわかれました。ということは頂点数がNからgcd(N, Ai)に減ったということになります。問題が少しだけ小さくなりました。

この操作を全ての頂点に対して行って、頂点数が１となれば、全部の頂点が同じグループに属するので、「連結可能となります」。もし、１よりも大きければ「連携不可能」です。

これで、連結判定部分はおしまいです。

今度は最適な構築方法です。最初に各操作のコストを１と固定した部分についてしっかりと考えます。この問題で重要となるのは「クラスカル法」というアルゴリズムです。このアルゴリズムは、平路を持たない連結なグラフにおいて辺の重みの総コストが最小となる「全域最小木」を構成するためのアルゴリズムです。とはいっても、その内容は次の通りです。

・グラフの辺を「コストが小さい順」に「閉路をつくらない」ように構成する

このようにコストの小さい辺から貪欲に採用することで、辺の重みが最小となるグラフが作れるんです。不思議ですね。

この辺の１つが本問題の操作１回に対応する

ので、このアルゴリズムを本問題に適用すると、

コストの小さいAiから順番にgcdを計算して頂点数を減らしていく

となります。また、このとき各Aiにおいては

N - gcd(N,Ai)

回の操作でグループ分けをすることができますので、そのときの総コストはこれにCiを掛けた値となります。

これを全ての操作に対して行い、コストを足し合わせていけば無事答えが求まります。繰り返しとなりますが、頂点数が１とならない場合には連結不可で -1 を出力してあげましょう。

実装

 #include <bits/stdc++.h> #define  rep(i,n) for(int i=0;i<n;++i) #define  reps(i,s,n) for(int i=s;i<n;++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
using T = tuple<int, int, int>;

int main()
{
	int n, m;
	cin >> n >> m;
	vector<P> p(m);
	for (auto& [c, a] : p) cin >> a >> c;
	sort(p.begin(), p.end());
	ll ans = 0;
	for (auto [c, a] : p)
	{
		ll g = gcd(n, a);
		ans += (n - g) * c;
		n = g;
	}

	if (n != 1) ans = -1;
	cout << ans << endl;
}

あとがき

私は最小公倍数に注目した方が理解しやすかったためこのような説明になりました。１ループの長さを求めて、それからグループ数を求めて、問題をどんどん小さくしていく、という感じです。まあ、やっていること、考え方は最大公約数と同じなんですけどね。