AtCoder Beginner Contest 065 D - Built?
解説ACしました...
問題
解法
解説の通り、愚直に考えると頂点本の辺からなる最小全域木を解くことが思いつくが、という制約下ではTLEしてしまう。しかし、x座標またはy座標で座標をソートした時、2つ以上離れた点同士のみを結ぶ辺のコストでその2つの点に加えて間の点を全て結ぶことができてしまうので、隣同士のみ辺を結べば十分であることが分かる。
結局これら本のエッジを張った後に最小全域木をクラスカル法などによって解けば十分実行時間制限に間に合う。2つの要素を一方の値でソートしたいときにはpairの配列を使えばよい。
コード
#include <bits/stdc++.h> using namespace std; struct union_find { vector<long long> par; //親の番号 vector<long long> rank; //木の深さ(根のランクは0) vector<long long> siz; //要素xが根なら木の頂点数を格納する //初期化子リストを用いた初期化 union_find(long long N) : par(N), rank(N), siz(N) { for (long long i = 0; i < N; i++) { par[i] = i; rank[i] = 0; siz[i] = 1; } } //要素xが所属する木の根を再帰的に発見する long long root(long long x) { if (par[x] == x) return x; return par[x] = root(par[x]); //経路圧縮 } //要素xが属する木と要素yが属する木の併合 void unite(long long x, long long y) { long long rx = root(x); long long ry = root(y); if (rx == ry) return; //同じ木に属してたらそのまま if (rank[rx] < rank[ry]) { par[rx] = ry; //根がryの木に併合 siz[ry] = siz[rx] + siz[ry]; } else { par[ry] = rx; //根がrxの木に併合 siz[rx] = siz[rx] + siz[ry]; if (rank[rx] == rank[ry]) rank[rx]++; } } //要素xが属する木と要素yが属する木が同じならtrueを返す bool same(long long x, long long y) { return root(x) == root(y); } //要素xが属する木の頂点数を返す long long size(long long x) { return siz[root(x)]; } }; /* クラスカル法 kruskal(V,E):無向グラフから最小全域木を作り使われる辺のコストを返す 使用するためにはunion_findが必要 計算量O(ElogV) */ struct kruskal_edge { long long u; long long v; long long cost; }; //辺のコストの大小を比較 bool kruskal_comp(const kruskal_edge &e1, const kruskal_edge &e2) { return e1.cost < e2.cost; } vector<kruskal_edge> kruskal_side; long long kruskal(long long V, long long E) //V:頂点数,E:辺数 { sort(kruskal_side.begin(), kruskal_side.end(), kruskal_comp); //辺のコストが小さい順にソート union_find kruskal_tree(V); long long kruskal_res = 0; for (long long i = 0; i < E; i++) { kruskal_edge ks = kruskal_side[i]; if (!kruskal_tree.same(ks.u, ks.v)) { kruskal_tree.unite(ks.u, ks.v); kruskal_res += ks.cost; } } return kruskal_res; } typedef long long ll; int main() { cout << fixed << setprecision(10); ll N; cin >> N; kruskal_side.resize(2 * (N - 1)); //edgeの本数だけ確保 map<pair<ll, ll>, ll> field; //ソート後に座標から頂点の番号を特定するのに必要 vector<pair<ll, ll>> xpairs(N); //x座標でソート用 vector<pair<ll, ll>> ypairs(N); //y座標でソート用 for (ll i = 0; i < N; i++) { ll a, b; cin >> a >> b; pair<ll, ll> P = make_pair(a, b), Q = make_pair(b, a); field[P] = i; xpairs[i] = P; ypairs[i] = Q; } sort(xpairs.begin(), xpairs.end()); sort(ypairs.begin(), ypairs.end()); ll now = 0; for (ll i = 0; i < N - 1; i++) { //xpairs kruskal_side[now].u = field[xpairs[i]]; kruskal_side[now].v = field[xpairs[i + 1]]; kruskal_side[now].cost = xpairs[i + 1].first - xpairs[i].first; now++; //ypairs //x座標とy座標を交換したものを用意(番号特定用に) pair<ll, ll> alter1 = make_pair(ypairs[i].second, ypairs[i].first); pair<ll, ll> alter2 = make_pair(ypairs[i + 1].second, ypairs[i + 1].first); kruskal_side[now].u = field[alter1]; kruskal_side[now].v = field[alter2]; kruskal_side[now].cost = ypairs[i + 1].first - ypairs[i].first; now++; } cout << kruskal(N, 2 * (N - 1)) << endl; return 0; }
AOJ 1127 - Building a Space Station
問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1127&lang=en
解法
各データセットが与えられるので、3次元空間における個の球体に対し任意の2点間を結ぶような本のエッジを張った後、クラスカル法などにより最小全域木問題を解けばよい。
中心の座標及び半径がそれぞれ
である2つの球間のコストは
となる。
コード
#include <bits/stdc++.h> using namespace std; struct union_find { vector<long long> par; //親の番号 vector<long long> rank; //木の深さ(根のランクは0) vector<long long> siz; //要素xが根なら木の頂点数を格納する //初期化子リストを用いた初期化 union_find(long long N) : par(N), rank(N), siz(N) { for (long long i = 0; i < N; i++) { par[i] = i; rank[i] = 0; siz[i] = 1; } } //要素xが所属する木の根を再帰的に発見する long long root(long long x) { if (par[x] == x) return x; return par[x] = root(par[x]); //経路圧縮 } //要素xが属する木と要素yが属する木の併合 void unite(long long x, long long y) { long long rx = root(x); long long ry = root(y); if (rx == ry) return; //同じ木に属してたらそのまま if (rank[rx] < rank[ry]) { par[rx] = ry; //根がryの木に併合 siz[ry] = siz[rx] + siz[ry]; } else { par[ry] = rx; //根がrxの木に併合 siz[rx] = siz[rx] + siz[ry]; if (rank[rx] == rank[ry]) rank[rx]++; } } //要素xが属する木と要素yが属する木が同じならtrueを返す bool same(long long x, long long y) { return root(x) == root(y); } //要素xが属する木の頂点数を返す long long size(long long x) { return siz[root(x)]; } }; struct kruskal_edge { long long u; long long v; double cost; }; //辺のコストの大小を比較 bool kruskal_comp(const kruskal_edge &e1, const kruskal_edge &e2) { return e1.cost < e2.cost; } vector<kruskal_edge> kruskal_side; double kruskal(long long V, long long E) //V:頂点数,E:辺数 { sort(kruskal_side.begin(), kruskal_side.end(), kruskal_comp); //辺のコストが小さい順にソート union_find kruskal_tree(V); double kruskal_res = 0; for (long long i = 0; i < E; i++) { kruskal_edge ks = kruskal_side[i]; if (!kruskal_tree.same(ks.u, ks.v)) { kruskal_tree.unite(ks.u, ks.v); kruskal_res += ks.cost; } } return kruskal_res; } int main() { cout << fixed << setprecision(3); while (true) { long long n; cin >> n; kruskal_side.resize(n * (n - 1) / 2); if (n == 0) break; vector<double> x(n); vector<double> y(n); vector<double> z(n); vector<double> r(n); for (long long i = 0; i < n; i++) cin >> x[i] >> y[i] >> z[i] >> r[i]; long long now = 0; for (long long i = 0; i < n; i++) { for (long long j = i + 1; j < n; j++) { kruskal_side[now].u = i; kruskal_side[now].v = j; double X = x[i] - x[j], Y = y[i] - y[j], Z = z[i] - z[j], R = r[i] + r[j]; kruskal_side[now].cost = max(0.0, (sqrt(X * X + Y * Y + Z * Z) - R)); now++; } } cout << kruskal(n, n * (n - 1) / 2) << endl; } return 0; }
ライブラリ置き場を作成しました
文章の投稿をするのは今回が初です...
拙いHTMLの知識で作ったwebページはGitHubで公開しました(スマホに対応していません...)
報告としてはここまでで完結しているので以降の自分語りは読む必要がないです()
作った理由
パソコンの操作すら覚束ない頃8月位に出会った競技プログラミングを始めてから、今日に至るまで惰性で8ヶ月弱の間コンテストに出続けて来ましたが、根本的なアルゴリズムの知識不足により、思うように問題が解けずレートも伸びない歯痒い思いをし続けてきたので、自分に喝を入れる目的(後モチベーションの維持)でライブラリを整備していこうと考えました。
正直ちゃんとした競プロ用のライブラリはインターネットを探せばあるのですが、いかんせん無知なので使い方が分からなかったり、ただ借りて解いても理解してなければ意味が無いのでは?という思いから、蟻本を写経しつつ読み進めてアルゴリズムの勉強をしながら、自分用にアレンジしたライブラリを制作するまでに至りました。しつこいようですが競プロ初心者なので書き方の作法(?)を理解しておらず、大変読みづらく使いづらいコードとなっています。(例えばマクロ名で指定した関数を使ってたり、関数テンプレートを使用してなかったりします...)
ライブラリ一覧
勝手に追加や修正をするので注意してください
後ライブラリの信頼性はゼロに等しいので普通に他の人のライブラリを使った方が賢明です。好奇心で使った場合の責任は持てません...
★がついてないライブラリはマクロ名で指定した関数を使用しているのでテンプレートなどが必要です(おいおい修正をかけます)
修正をかけました。(2020-04-30)同時に★を全て削除しましたが、多分普通に使えるようになったと思います。
グラフアルゴリズム
データ構造
数学
おまけ
最後に
プログラミング未経験の自分が、半年も競技プログラミングにハマり続けることができた理由としては、やはりコンスタントに日本語のコンテストを開催してくれるAtcoderの存在や、qlitaやSNSなどで情報を提供してくれるユーザーの存在が大きいです。コンテスト参加者もここ最近で急増していますし、初心者への門戸を開く礎を築いてくれた上級者の方々には感謝しきれません。
次の記事では水色になった報告が出来るように、これからも精進を続けたいと思います。こんな駄文をここまで読んで下さり、ありがとうございました。
これからもよい競プロライフを!
Atcoder緑になりたい
↑わかる
投稿テスト
(。ŏ﹏ŏ)