C++の練習を兼ねて, AtCoder Regular Contest 064 の 問題E (Cosmic Rays) を解いてみた.
■感想.
1. 問題E は, 解答方針が, 全く見えなかったので, 解答を参照して, 実装して何とかAC版となった.
2. ダイクストラ法の復習が出来たので, 非常に良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトARC 064 解説をご覧下さい.
■C++版プログラム(問題E/AC版).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 |
// 解き直し. // https://img.atcoder.jp/arc064/editorial.pdf // テストケース(1_12.txt) などで, TLE版となったため, ロジック修正. // AtCoder Beginner Contest 051 (D - Candidates of No Shortest Paths) で 実装した ダイクストラ法 を 一部流用. #include <bits/stdc++.h> using namespace std; #define repex(i, a, b, c) for(int i = a; i < b; i += c) #define repx(i, a, b) repex(i, a, b, 1) #define rep(i, n) repx(i, 0, n) #define repr(i, a, b) for(int i = a; i >= b; i--) #define pb push_back #define a first #define b second // cost を 2次元配列 から 1次元配列 に 変更. double cost[1010]; // 頂点 0 から 各頂点まで の 最小コスト を 保存. double x[1010], y[1010], r[1010]; // バリア情報. double b[1010][1010]; // バリア i, j の 中心を結ぶ辺のコスト. struct edge { int u; // 次の頂点. double d; // コスト. bool operator < (const edge &E) const { return d > E.d; } }; vector<edge> G[1010]; // https://ja.wikipedia.org/wiki/ダイクストラ法 // グラフを最良優先探索する. // ※dijkstraの動作確認用. // @param s: 今回探索する頂点番号. // @return: 特に無し. void dijkstra(int s){ // 1. 初期化. priority_queue<edge> pq; // 2. 始点設定. pq.push({s, 0.0}); cost[s] = 0.0; // 3. キュー pq が 空になるまで, 探索. while(!pq.empty()){ // 4. 探索を継続するために, 頂点を取得. int u = pq.top().u; // 頂点番号. double d = pq.top().d; // コスト. pq.pop(); // 5. より小さいコストが設定済みなら, Skip. if(cost[u] < d) continue; // 6. 各隣接する頂点について, コストを確認し, 最短コストを更新. rep(i, G[u].size()){ int nu = G[u][i].u; double nd = d + G[u][i].d; // 最短コスト更新. if(cost[nu] > nd) cost[nu] = nd, pq.push({nu, nd}); } } } int main(){ // 1. 入力情報. double xs, ys, xt, yt; int N; scanf("%lf %lf %lf %lf %d", &xs, &ys, &xt, &yt, &N); rep(i, N) scanf("%lf %lf %lf", &x[i + 1], &y[i + 1], &r[i + 1]); x[0] = xs, y[0] = ys, x[N + 1] = xt, y[N + 1] = yt; // 2. 辺のコストを事前計算. rep(i, N + 1){ repx(j, i + 1, N + 2){ double w = max(0.0, hypot(x[i] - x[j], y[i] - y[j]) - (r[i] + r[j])); b[i][j] = w; b[j][i] = w; } } // 3. グラフ作成. // 頂点が, 0, 1, ... , N, N + 1 までの (N + 2)頂点あると見る. rep(i, N + 1){ repx(j, i + 1, N + 2){ G[i].pb({j, b[i][j]}); G[j].pb({i, b[j][i]}); } } // 4. ダイクストラ法. rep(i, 1010) cost[i] = 202020202020202020.0; dijkstra(0); // 5. 出力. printf("%.10f\n", cost[N + 1]); return 0; } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
[入力例] -2 -2 2 2 1 0 0 1 [出力例] 3.6568542495 ※AtCoderのテストケースより [入力例] -2 0 2 0 2 -1 0 2 1 0 2 [出力例] 0.0000000000 ※AtCoderのテストケースより [入力例] 4 -2 -2 4 3 0 0 2 4 0 1 0 4 1 [出力例] 4.0000000000 ※AtCoderのテストケースより [入力例] 123 45 -67 -89 10 3 1 4 15 9 2 6 5 3 58 97 9 32 38 4 62 64 3 383 279 50 28 84 1 97 16 9 39 93 7 [出力例] 215.6818349357 |
■参照サイト
AtCoder Regular Contest 064