ミケ猫の小部屋

情報学、数学、語学および料理(暫定)について発信します

ICPC2020国内予選のFに挑んでみた!

11/06にICPC国内予選に参加して、三問完で何とかギリギリ予選突破しそうなみけ(チームxjubichanx)です。試合最中にFが昔のJOIのある問題とよく似ていることに気づきながらも解けなかった。

挑戦の第一歩:基本方針

始まる前に、まずは問題を目に通してください。

icpc.iisf.or.jp

一番ナイーブな方法は、災難レベルを0から徐々に上げていく。そして災難レベルごとにグラフのコンポーネントを計算して、サイズが一番大きいコンポーネント以外のコンポーネントをフィルターアウトしていく。災難レベルごとにDFSする必要があるため、計算量は恐らくO(M(N+M))になる。通称TLEってことです。

では、コンポーネントを増量的に探していこう。災難レベルを段々に上げて、そして災難レベル以下のエッジを削除してコンポーネントを段々小さいコンポーネントに分けていくことは難しいだろうと思う。なぜなら、一つのエッジを削除しても他のエッジが二つのサブコンポーネントの間にあるかもしれない。一つのエッジがある二つのコンポーネントを繋ぐ最後の「橋」を確認することは時間がかかる(DFSする必要があるので、計算量はさらにN+Mがかけられる)。

そこで、私は閃いた!災難レベルを初めから高く設定して、各頂点を最初から孤立する。その後、災難レベルを徐々に下げて頂点たちを繋いでいく。なので、推定強度の高いエッジから見に行って、エッジをグラフに加入していく。最初はN個の頂点それぞれ自分のコンポーネントにいるけど、エッジの加入によって小さいコンポーネントは段々大きいコンポーネントになる。 加入によるコンポーネントの融合タイミングはO(1)で判別できる

もし一つのエッジの二つの頂点は違うコンポーネントにいるなら、そのエッジの加入は二つのコンポーネントの融合に繋ぐ。つまり頂点が同じコンポーネントにいるかを判別し、融合をするタスクがメインです。この場合はUnion-FindでO(1)の判別と融合ができる。

挑戦の第二歩:エッジを昇順で見に行く

先までは推定強度の高いやつからコンポーネントを探していましたが、その方法で探したコンポーネントには致命的な冗長がある。

バックから見たコンポーネントは必ずしも存在しない*1

その問題を解決するため、最初は後ろから見て各辺は二つのコンポーネントをつなぐかどうかそして二つのコンポーネントのサイズを記録する。昇順でエッジを削除する時、コンポーネントのマージは分裂になる。その記録により、分裂のタイミングと分裂したコンポーネントのサイズはすぐにわかる。

昇順でエッジを見に行く最中、各災難レベルでの最大コンポーネントサイズはすぐにわかる。その後すぐにその推定強度のエッジをもう一回見て、分裂すべきエッジ*2なら分裂した後のコンポーネントのサイズによる頂点の削除を行う。分裂した後のコンポーネントのサイズがこの災難レベルでの最大コンポーネントのサイズより小さいだったらすべての点にタイムスタンプを付ける。

挑戦の第三歩:チェックメート

残ることはどうやら全ての頂点を見てタイムスタンプのもっとも大きいやつを出力するだけだと思ったら、サンプル出力に合わないところが現れた!もし、答えとなる集合は推定強度のもっとも高いエッジで繋がっているならどうなる?たぶん最後までも「削除」されないだろう。そのエッジを潰したら、残るコンポーネントはどれもサイズ1なので、最後までも削除されない。そのため、タイムスタンプが0(削除されないためタイムスタンプがおかしい)の頂点には一番大きいタイムスタンプを付けておきたい。

その最後の一歩が完成すれば、残りは小さい順から頂点を見てタイムスタンプの一番大きいやつを出力する。

コード

コンテスト中には解けなかったので、正解かどうかはわからないまま。ここでコードを貼り付けて、間違いがあれば指摘お願いします。

#include <cstdio>
#include <queue>
#include <utility>
#include <memory>
#include <map>
#include <algorithm>

using namespace std;

const int MAXN=1e5+7;

int UF[MAXN];
int sz[MAXN];

int parent(int n){
    // printf("%d\n",n);
    if (UF[n]==0) return n;
    else {
        auto ret=parent(UF[n]);
        UF[n]=ret;
        return ret;
    }
}

using E=pair<int,pair<int,int>>;

int N,M;

vector<pair<int,int>> graph[MAXN];
E edges[MAXN];//s a b
pair<int,int> partition_sz[MAXN];//sza szb

int height[MAXN];
int h,w;

void DFS(int cur,int c=0){
    if (c>=3) return;
    auto &vis=height[cur];
    if (vis) return;

    vis=h;
    // printf("height[%d]=%d h=%d\n",cur,height[cur],h);
    for(auto adj:graph[cur]) {
        if (adj.second<=w) continue;
        DFS(adj.first,c+1);
    }
}

bool judge(const map<int,int>& m){
    return m.crend()->second==1;
}

int main(){

    while(scanf("%d%d",&N,&M)&&N){
        
        map<int,int> count;
        count[N]=1;

        h=0;
        for(int i=1;i<=N;i++){
            sz[i]=1;
            UF[i]=0;
            graph[i].clear();
            height[i]=0;
        }

        for(int i=1;i<=M;i++){
            int a,b,s;
            scanf("%d%d%d",&a,&b,&s);
            edges[i]=E{s,{a,b}};
            graph[a].push_back(pair<int,int>(b,s));
            graph[b].push_back(pair<int,int>(a,s));

            partition_sz[i]=pair<int,int>(0,0);
        }

        sort(edges+1,edges+M+1);

        int i=M;
        while(i>0){
            auto weight=edges[i].first;

            int j=i;
            while(j>0&&edges[j].first==weight){
                auto edge=edges[j].second;
                auto pa=parent(edge.first),pb=parent(edge.second);
                auto &part=partition_sz[j];
                j--;
                if (pa==pb&&(pa!=0)) continue;


                auto sza=sz[pa],szb=sz[pb];
                
                // printf("sza=%d szb=%d\n",sza,szb);
                part=pair<int,int>(sza,szb);
                
                UF[pb]=pa;
                sz[pa]+=sz[pb];
            }
            i=j;
        }


        //昇順
        i=1;
        while(i<=M){
            auto weight=edges[i].first;
            w=weight;
            h++;

            int j=i;
            // for(auto kv:count){
            //     printf("k=%d v=%d\n",kv.first,kv.second);
            // }
            while(j<=M&&edges[j].first==weight){
                auto edge=edges[j].second;
                auto a=edge.first,b=edge.second;
                auto &part=partition_sz[j];
                j++;
                //このエッジがコンポーネントを二つに分けていないなら次
                if (!part.first||!part.second) continue;
                if (height[a]||height[b]) continue;

                auto sza=part.first,szb=part.second,sum=sza+szb;
                
                // printf("a=%d b=%d sza=%d szb=%d\n",a,b,sza,szb);
                if (--count[sum]==0) count.erase(sum);
                count[sza]++,count[szb]++;

            }

            auto max_size=count.rbegin()->first;
            
            // printf("max_size=%d\n",max_size);
            // puts("loop");
            for(int k=i;k<j;k++){
                auto edge=edges[k].second;
                auto a=edge.first,b=edge.second;
                auto const &part=partition_sz[k]; 

                if (!part.first||!part.second) continue;
                if (height[a]&&height[b]) continue;
                auto sza=part.first,szb=part.second,sum=sza+szb;
                
                // puts("dfs");
                if (sza<max_size&&!height[a]) 
                    DFS(a);
                if (szb<max_size&&!height[b]) 
                    DFS(b);
            }

            auto occurences=count.rbegin()->second;
            count.clear();
            count[max_size]=occurences;
            i=j;
        }


        for(int i=1;i<=N;i++) if (height[i]==0) height[i]=h;
        auto max_height=(*max_element(height+1,height+N+1));
        
        
        for(int i=1;i<=N;i++) if (height[i]==max_height) printf("%d ",i);
        putchar('\n');

    }

    return 0;
}

*1:

例として、1級災難AとBの二つのコンポーネントがいるとする。Aは7個の頂点からなる。Bは6個の頂点の頂点からなる。なのでBはAより不安全。でも、災難レベルがさらに上げると、Aは縮小して3個の頂点になる。Bはまた6個の頂点からなる。

バックから見れば、Bはどのコンポーネントの一部だったとかの情報はわからない。なのでBが存在しないコンポーネントということは知らない。

*2: バックからのトラバーサルで分裂するとマークされる以外も、削除された二つの頂点の間にいないことも重要。前言った存在しないコンポーネントを排除するためです