C++の練習を兼ねて, AtCoder Regular Contest 043 の 問題A (点数変換) ～ 問題B (難易度) を解いてみた.
■感想.
1. 問題B は, 2倍以上の線引きが, ややこしい感じがしたが, 何とかAC版となった.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトARC 043 解説をご覧下さい.
■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 31 32 33 34 35 36 |
#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 main(){ // 1. 入力情報. int N; double A, B, d, sSum = 0.0, sMax = 0.0, sMin = 1234567890.0; scanf("%d %lf %lf", &N, &A, &B); rep(i, N){ scanf("%lf", &d); sSum += d; sMax = max(sMax, d); // 最大値. sMin = min(sMin, d); // 最小値. } // 2. P, Q を 計算. // N * A = P * sSum + N * Q; // B = (P * sMax + Q) - (P * sMin + Q) // -> P = B / (sMax - sMin), Q = A - P * sSum / N で 計算. double P = -1.0, Q = -1.0, ans = 0.0; if(sMax != sMin){ P = B / (sMax - sMin); Q = A - P * sSum / (N + 0.0); } // 3. 出力. if(P == -1.0 && Q == -1.0) puts("-1"); else printf("%.12lf %.12lf\n", P, Q); 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 |
[入力例] 5 2 4 2 4 6 8 10 [出力例] 0.5 -1 ※AtCoderのテストケースより ※ 但し, 上記のプログラムでは, 以下の内容が出力される. 0.500000000000 -1.000000000000 [入力例] 13 29 31 3 1 4 1 5 9 2 6 5 3 5 8 9 [出力例] 3.875 10.8173076 ※AtCoderのテストケースより ※ 但し, 上記のプログラムでは, 以下の内容が出力される. 3.875000000000 10.817307692308 [入力例] 5 1 2 34 34 34 34 34 [出力例] -1 ※AtCoderのテストケースより [入力例] 30 27 182 8 18 28 45 90 4 5 2 35 3 60 287 47 135 266 24 977 57 24 70 9 36 9 995 9 57 49 669 67 627 [出力例] 0.183282980866 -1.787646861363 |
■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 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 |
#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--) #define pb push_back #define all(x) x.begin(), x.end() const LL MOD = 1e9 + 7; vector<int> v; LL a[101010], aCum[101010], hCum[101010], hhCum[101010]; int main(){ // 1. 入力情報. int N, d; scanf("%d", &N); rep(i, N){ scanf("%d", &d); v.pb(d); } // 2. sort. sort(all(v)); // 3. 半分以下となるindexを保存. rep(i, N){ int h = v[i] / 2; int at = upper_bound(all(v), h) - v.begin(); a[i] = (LL)at; } // rep(i, N + 1) printf("%lld ", a[i]); // puts(""); // 4. 累計和. rep(i, N) aCum[i + 1] = (aCum[i] + a[i]) % MOD; // rep(i, N + 1) printf("%lld ", aCum[i]); // puts(""); // 5. 半分以下となる累積和を保存. rep(i, N){ int h = v[i] / 2; int at = upper_bound(all(v), h) - v.begin(); hCum[i] = aCum[at]; } // rep(i, N + 1) printf("%lld ", hCum[i]); // puts(""); // 6. 5. の 累計和 の 累積和を保存. rep(i, N) hhCum[i + 1] = (hhCum[i] + hCum[i]) % MOD; // rep(i, N + 1) printf("%lld ", hhCum[i]); // puts(""); // 7. 集計. LL ans = 0; rep(i, N){ int h = v[i] / 2; int at = upper_bound(all(v), h) - v.begin(); ans += hhCum[at]; ans %= MOD; } // 8. 出力. printf("%lld\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 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 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 |
[入力例] 5 1 2 4 5 10 [出力例] 2 ※AtCoderのテストケースより [入力例] 10 11 12 13 14 15 16 17 18 19 20 [出力例] 0 ※AtCoderのテストケースより [入力例] 20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 [出力例] 94 ※AtCoderのテストケースより [入力例] 17 1 3 7 18 19 23 37 39 50 53 55 63 72 85 87 105 110 [出力例] 212 [入力例] 100 79519 45104 92509 88993 73459 82441 78447 21618 18167 57392 20514 31090 61541 24092 79667 47425 6689 83972 75832 69279 30799 20074 51059 98080 55339 84087 62943 98661 42657 4574 29955 17482 56286 46274 22401 96276 40863 85030 69246 68506 64931 74823 54176 47158 10242 25825 68095 6372 83795 92613 19488 55125 48684 68880 48189 25955 81713 65094 65779 1236 19761 6899 26202 57969 64253 35921 2839 62866 22114 64452 25979 7147 26216 59430 69052 35355 48987 22713 22231 13039 46748 46309 77394 49393 97296 66248 77680 57653 68937 49131 57185 18608 49244 75533 41120 74204 94321 37535 14720 22327 [出力例] 28140 |
■参照サイト
AtCoder Regular Contest 043