裏紙

ほぼ競プロ、たまに日記

CODE FESTIVAL 2016 Final G - Zigzag MST

問題

G: Zigzag MST - CODE FESTIVAL 2016 Final (Parallel) | AtCoder

問題概要

頂点がN個のグラフがあり、0からNまで番号が順に付けられている。初期状態で辺は無く、以下のような辺追加クエリがQ個来る。

頂点番号ABと重みCが与えられて、

  • ABに重みCの辺を張る。
  • Aのindexを1つ進めて、A+1Bに重みC+1の辺を張る。
  • Bのindexを1つ進めて、A+1B+1に重みC+2の辺を張る。
  • Aのindexを1つ進めて、A+2B+1に重みC+3の辺を張る。
  • Bのindexを1つ進めて、A+2B+2に重みC+4の辺を張る。

という操作を以下同様に無限回繰り返す(ただし、このindexをすすめる時はmod N上で行う)。

このクエリが全て来た後の最小全域木に含まれる辺の重みの総和を答えよ。

  •  2 \le N \le 200000
  •  1 \le Q \le 200000
  •  0 \le A,B \le N-1
  •  1 \le C \le 10^9

イデア

当日の会場の解説スタジオで聞いて、すごく綺麗な解答で口頭でしゃべっていたことも合わせて聞くととても自然に納得し理解できたので忘れないうちにまとめておこうと思った。

問題文上では無限回繰り返されることになっているが、一周以上しても多重辺になるだけで、コストは単調増加していくのでMSTを構成するにあたっては小さい方が残っていれば良い。

さて、1周分を考えてみると1つのクエリは次のような辺を張っていることになる↓

f:id:imulan:20161129010614p:plain

このクエリが全て読み込まれて、MSTを構成していこうという状況を考えるときに、クラスカル法でMSTを構成していくことを考えると、A+1Bの間にある重みC+1の辺がMSTとして入るかどうかはA+1Bが連結されているかどうかに依存していることになるわけだが、そのBに注目するとBAと重みCの辺で繋がっている。つまり、このC+1の辺を考慮する前の段階ですでにこの辺を使うかどうかが考慮されているわけで、使うか否かに関わらず、このC+1の辺をMSTの辺として採用するのかを判定する段階において、必ずABは連結になっているわけなので、A+1Bの間に張られた辺をtex:A+1]とAの間に張り直しても状況は変化しない。そして、張り替えると次のようになる↓

f:id:imulan:20161129011447p:plain

そうすると、同じ理由によってC+2の辺がBB+1の間の辺とすることが出来る↓

f:id:imulan:20161129011600p:plain

以下同様に、この操作を繰り返していくと次のようにABの間に重みCの辺があり、そのほかは頂点番号が隣接しているところに等差が2で辺が張られていくというようなクエリに変換されることになる↓

f:id:imulan:20161129012224p:plain

そうすると、Q個のクエリを受けると、最終的にはそれぞれのクエリの始点ABの間に張られる重みCの辺がO(Q)個と、N個の頂点の隣接しているところを結ぶN個の辺の合計O(Q+N)個の辺でこのグラフが構成されることになり、この辺の個数ならクラスカル法によってMSTを求めることが可能である。

最後に、この輪のように構成されるN個の辺について、Q重になっているわけだがその中で最小のものを残すようにしたい。それは、重みが等差であることを利用して次のようにDPで求めることが出来る。

dp[i] = 頂点iと頂点(i+1)を繋ぐ辺の重みの最小値として、全てを十分大きい値で初期化し、その次にdp[A]C+1dp[B]C+2と最小値更新をかけていく。

そして、等差であることを利用すればdp[i] = min(dp[i], dp[i-1]+2)という更新を2周すればこの輪について重みが最小の辺を構成することがO(N)で出来る。

実装(C++)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

struct UF{
    int n;
    //正だったらその頂点の親,負だったら根で連結成分の個数
    vector<int> d;
    UF() {}
    UF(int N):n(N), d(N,-1){}
    int root(int v){
        if(d[v]<0) return v;
        return d[v]=root(d[v]);
    }
    bool unite(int X,int Y){
        X=root(X); Y=root(Y);
        if(X==Y) return false;
        if(size(X) < size(Y)) swap(X,Y);
        d[X]+=d[Y];
        d[Y]=X;
        return true;
    }
    int size(int v){ return -d[root(v)]; }
    bool same(int X,int Y){ return root(X)==root(Y); }
};

const int N=200000;
const ll INF=123456789012345LL;
ll dp[N];

typedef pair<int,int> pi;
typedef pair<ll,pi> edge;
vector<edge> e;

int main()
{
    int n,Q;
    scanf(" %d %d", &n, &Q);

    fill(dp,dp+N,INF);

    while(Q--)
    {
        int a,b;
        ll c;
        scanf(" %d %d %lld", &a, &b, &c);

        e.pb(edge(c,pi(a,b)));
        dp[a]=min(dp[a],c+1);
        dp[b]=min(dp[b],c+2);
    }

    rep(_,2)rep(i,n) dp[i]=min(dp[i], dp[(i-1+n)%n]+2);
    rep(i,n) e.pb(edge(dp[i],pi(i,(i+1)%n)));

    sort(all(e));

    UF uf(n);
    ll ans=0;
    rep(i,e.size())
    {
        int a=e[i].se.fi, b=e[i].se.se;
        if(!uf.same(a,b))
        {
            uf.unite(a,b);
            ans+=e[i].fi;
        }
    }
    printf("%lld\n", ans);
    return 0;
}