C++の練習を兼ねて, 競プロ典型 90 問 の 問題070 (Plant Planning) を解いてみた.
■感想.
1. 問題070は, 規則性を抽出できたので, AC版に到達出来たと思う.
2. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.
詳細は, 本家のサイト(GitHub) 競プロ典型 90 問 の 問題070 を ご覧下さい.
■C++版プログラム(問題070／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 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; #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--) LL x[101010], y[101010], xCum[101010], yCum[101010]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N) scanf("%lld %lld", &x[i], &y[i]); // 2. sort. sort(x, x + N); sort(y, y + N); // 3. 累積和. rep(i, N) xCum[i + 1] = xCum[i] + x[i]; rep(i, N) yCum[i + 1] = yCum[i] + y[i]; // 4. 最小値となる座標を選択. // 4-1. X軸方向. LL xL1 = 202020202020202020; rep(i, N){ // i番目の座標を基準とした場合のマンハッタン距離. LL mx = 0; mx += x[i] * (i + 1) - xCum[i]; // 前半. mx += xCum[N] - xCum[i + 1] - x[i] * (N - i); // 後半. // 最小値更新. xL1 = min(xL1, mx); } // 4-2. Y軸方向. LL yL1 = 202020202020202020; rep(i, N){ // i番目の座標を基準とした場合のマンハッタン距離. LL my = 0; my += y[i] * (i + 1) - yCum[i]; // 前半. my += yCum[N] - yCum[i + 1] - y[i] * (N - i); // 後半. // 最小値更新. yL1 = min(yL1, my); } // 5. 出力. printf("%lld\n", xL1 + yL1); 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 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 |
[入力例] 2 -1 2 1 1 [出力例] 3 ※AtCoderテストケースより [入力例] 2 1 0 0 1 [出力例] 2 ※AtCoderテストケースより [入力例] 5 2 5 2 5 -3 4 -4 -8 6 -2 [出力例] 35 ※AtCoderテストケースより [入力例] 4 1000000000 1000000000 -1000000000 1000000000 -1000000000 -1000000000 1000000000 -1000000000 [出力例] 8000000000 ※AtCoderテストケースより [入力例] 10 21 -56 12 3 -85 109 52 83 74 -104 74 60 -27 23 115 26 48 -31 -33 56 [出力例] 974 [入力例] 20 1071 -547 -1209 955 471 619 11 -274 616 945 398 947 74 -719 -791 116 553 895 963 1123 1169 -588 351 263 -1074 1168 -194 472 74 983 335 -87 20 -759 250 109 -703 87 110 125 [出力例] 20766 [入力例] 30 36482 -23698 389 35575 -62928 92676 122078 54909 28165 109096 -73226 57941 105357 48524 20055 -58032 16498 16028 117248 -52570 11791 90614 77697 80036 -85345 99427 79997 112720 41282 21973 5960 38768 -101579 35767 59552 105905 -6496 8393 21473 57496 54252 -16542 10940 21207 11230 -52560 15006 25961 99768 95712 -96551 894 31111 41698 -36617 114873 123235 -61626 120138 -73622 [出力例] 2861955 |
■参照サイト
070 – Plant Planning