Ring MST [AtCoder Beginner Contest 210 E]

https://atcoder.jp/contests/abc210/tasks/abc210_e

前提知識

• クラスカル法(MST, 最小全域木)

解説

https://atcoder.jp/contests/abc210/submissions/24333006

題名にもあるように今回はMST,最小全域木を作ることが目的となっている。
上手く隠されているような感じがするが、クラスカル法を前提として問題を解くことができる。
クラスカル法についてはそれほど説明しないので、他で勉強することを勧める。
ちょっとだけ触れるし、核の部分ではないので、必須ではないかと思うが…どうだろう…

クラスカル法

クラスカル法とは、最小全域木を作るアルゴリズムの1つで、使える辺の中でコストが最小のものから連結でないなら
使っていくというアルゴリズムである。
今回で言うとM種類の操作について費用が少ないものから使用を検討していくことにする。
とりあえず、M種類の操作は費用が少ない順でソートされているとこれ以降は考える。

とある操作を行うとき

クラスカル法なので、とある操作を行うときに連結成分を減らせるだけ減らすように毎回行っていく。
例えば、N=6でA=2の場合を考えてみる。

1->3  
2->4  
3->5  
4->6  
5->1  
6->2  

これで連結になる辺を先頭から順に選択すると最初の4つが使える。
最後の2つはすでに連結なので必要ない。
こうすると、2つの連結成分になるので、N=2になったと考えてもいい。

ここがほんとかポイントなのだが、例えばこの状態でA=3を考えてみると、

1->4  
2->5  
3->6  
4->1  
5->2  
6->3  

となり、連結している中で最小の数に変換したと考えると

1->2  
2->1  
1->2  
2->1  
1->2  
2->1  

となり、実質

1->2  
2->1  

なので、連結成分数を操作後のNとしてしまっても問題ない。

操作前にNで、とある操作がAであるとすると、最適に操作をすると連結成分数はgcd(N,A)となる。
これは今までに何となく似たような問題を見てきたのと、実験と、色々加味してひねり出した。

まとめ

説明が冗長になってきたので、まとめる。
操作は費用が少ない順に実施して、毎回の操作で、操作前の連結成分数がcurで、操作Aを行ったとすると、
連結成分数はgcd(cur, A)になり、その際に行われる操作回数はその差分なので、cur-gcd(cur,A)回。
つまり、かかる費用は(cur-gcd(cur,A))×Cとなる。
これの総和がかかる必要の総和となる。

最終的に連結成分数curが1でないなら、MSTが構築できていないので、-1を答えとする。

int N, M, A[101010], C[101010];
vector<pair<int, int>> CA;
//---------------------------------------------------------------------------------------------------
ll solve() {
    rep(i, 0, M) CA.push_back({ C[i], A[i] });
    sort(all(CA));

    int cur = N;
    ll ans = 0;
    fore(p, CA) {
        int c = p.first;
        int a = p.second;

        ans += 1LL * (cur - gcd(cur, a)) * c;
        cur = gcd(cur, a);
    }

    if (cur == 1) return ans;
    return -1;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, M) cin >> A[i] >> C[i];
    cout << solve() << endl;
}