C++の練習を兼ねて, AtCoder Regular Contest 004 の 問題A (A – 2点間距離の最大値 ( The longest distance )) ～ 問題B (B – 2点間距離の最大と最小 ( Maximum and Minimum )) を解いてみた.
■感想.
1. 問題B は, 方針決まるまで時間かかったものの, 一番長い辺を固定すれば解けることに気付いたので, AC版となった.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
■C++版プログラム(問題A／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 |
#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 a first #define b second pair<double, double> p[111]; int main(){ // 1. 入力情報. int N; double x, y; scanf("%d", &N); rep(i, N){ scanf("%lf %lf", &x, &y); p[i] = {x, y}; } // 2. 最も長くなる線分の長さは？ double ans = 0.0; rep(i, N - 1) repx(j, i + 1, N) ans = max(ans, hypot(p[i].a - p[j].a, p[i].b - p[j].b)); // 3. 出力. printf("%.12lf\n", ans); 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 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 |
[入力例] 3 1 1 2 4 4 3 [出力例] 3.605551 ※AtCoderのテストケースより ※上記のプログラムだと以下のように出力される. 3.605551275464 [入力例] 10 1 8 4 0 3 7 2 4 5 9 9 1 6 2 0 2 8 6 7 8 [出力例] 10.630146 ※AtCoderのテストケースより ※上記のプログラムだと以下のように出力される. 10.630145812735 [入力例] 4 0 0 0 100 100 0 100 100 [出力例] 141.421356 ※AtCoderのテストケースより ※上記のプログラムだと以下のように出力される. 141.421356237310 [入力例] 5 3 0 1 0 0 0 4 0 2 0 [出力例] 4.000000 ※AtCoderのテストケースより ※上記のプログラムだと以下のように出力される. 4.000000000000 [入力例] 4 2 2 0 0 1 1 3 3 [出力例] 4.242641 ※AtCoderのテストケースより ※上記のプログラムだと以下のように出力される. 4.242640687119 |
■C++版プログラム(問題B／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 |
#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--) int d[555]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N) scanf("%d", &d[i]); // 2. sort. sort(d, d + N); // 3. 0番目, N番目の距離 で 取り得る値の最大, 最小は？ // 3-1. 最大. int aMax = 0; rep(i, N) aMax += d[i]; // 3-2. 最小. // ※ 一番長い辺を固定して考える. int aMin = d[N - 1] - (aMax - d[N - 1]); if(aMin < 0) aMin = 0; // 4. 出力. printf("%d\n%d\n", aMax, aMin); 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 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 |
[入力例] 1 1024 [出力例] 1024 1024 ※AtCoderのテストケースより [入力例] 3 3 4 5 [出力例] 12 0 ※AtCoderのテストケースより [入力例] 2 512 512 [出力例] 1024 0 ※AtCoderのテストケースより [入力例] 3 4 8 1 [出力例] 13 3 ※AtCoderのテストケースより [入力例] 10 1 2 3 4 5 6 7 8 9 10 [出力例] 55 0 ※AtCoderのテストケースより [入力例] 5 10 12 30 32 100 [出力例] 184 16 [入力例] 10 6 7 8 8 7 9 10 10 12 111 [出力例] 188 34 |
■参照サイト
AtCoder Regular Contest 004