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版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?
- 作者: 秋葉拓哉,岩田陽一,北川宜稔
- 出版社/メーカー: マイナビ
- 発売日: 2012/01/28
- メディア: 単行本(ソフトカバー)
- 購入: 25人 クリック: 473回
- この商品を含むブログ (36件) を見る