D - Built? (arc076_b) クラスカル法で解いた

Quiz

https://atcoder.jp/contests/abc065/tasks/arc076_b

Submit

https://atcoder.jp/contests/abc065/submissions/3924290

Step1

  • 解説pdfの通り、X, Yでそれぞれソートしてエッジを貼ればエッジ数O(N)になることに気づく

Step2

  • 最小全域木の構築
    • クラスカル法
    • プリム法
  • 今回はクラスカル法を選択

ミス1

    sort(ALL(P), Point::sortByX);
    FOR(i, 0, N-1){
        Edge edge;
        edge.from = P[i].id;
        edge.to = P[i+1].id;
        edge.cost = min(abs(P[i].x - P[i+1].x), abs(P[i].y - P[i+1].y));
        edgeList.push_back(edge);
    }

    sort(ALL(P), Point::sortByY);
    FOR(i, 0, N-1){
        Edge edge;
        edge.from = P[i].id;
        edge.to = P[i+1].id;
        edge.cost = min(abs(P[i].x - P[i+1].x), abs(P[i].y - P[i+1].y));
        edgeList.push_back(edge);
    }
  • これで同じコードをコピペするのが嫌だなと思い、2回だけ回るforを追加したが、同じ添え字 i を使ってしまった
  • たしかRE (Runtime Error)を引き起こした

ミス2

    static bool sortByY(Point a, Point b){
        if(a.y == b.y){
            return a.x < a.x;
        }else{
            return a.y < b.y;
        }
    }
  • 比較関数にて、書き間違えて return a.x < b.y などと書いていた
  • 意味不明なソートになるので止まらなくなりRE

ミス3

    // 短いエッジから見ていって必要なら連結
    for(auto edge : edgeList){

        if(findRoot(edge.from) == findRoot(edge.to)){
            // skip
        }
        else{
            // つなぐ
            _union(findRoot(edge.from), findRoot(edge.to));
            cost_sum += edge.cost;
        }
    }
  • つなぐとき、_union(edge.from, edge.to) としていた
  • 子供をUnionしても意味ない!親をUnionしないと

最後に

  • ということで色々ミスが重なり、かなり時間がかかった
  • ACして報われた

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?