C++の練習を兼ねて, AtCoder Regular Contest 122 の 問題B (Insurance) を解いてみた.
■感想.
1. 規則性を抽出できたので, AC版に到達出来たと思う.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 122 解説 の 各リンク を ご覧下さい.
■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 |
// 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 a[101010], aCum[101010]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N){ scanf("%lld", &a[i]); a[i] *= 2; } // 2. sort. sort(a, a + N); // 3. 累積和. rep(i, N) aCum[i + 1] = aCum[i] + a[i]; // 4. 期待値の最小化を計算. LL t = 202020202020202020; rep(i, N){ LL x = a[i] / 2; LL l = N * x + aCum[N] - (N - i) * a[i] - aCum[i]; t = min(t, l); } // 5. 出力. double ans = (double)t / (double)(N * 2.0); 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 |
[入力例] 3 3 1 4 [出力例] 1.83333333333333333333 ※AtCoderのテストケースより ※但し, 上記のプログラムでは, 以下の内容が出力される. 1.833333333333 [入力例] 10 866111664 178537096 844917655 218662351 383133839 231371336 353498483 865935868 472381277 579910117 [出力例] 362925658.10000000000000000000 ※AtCoderのテストケースより ※但し, 上記のプログラムでは, 以下の内容が出力される. 362925658.100000023842 [入力例] 30 180 214 268 205 256 151 318 244 251 85 285 101 3 105 64 20 68 267 102 40 104 150 200 126 21 169 269 37 272 254 [出力例] 121.733333333333 [入力例] 50 50568 31661 5354 6042 40506 15410 23562 36883 38669 29863 39256 36598 23453 7072 45569 14763 8168 50811 12511 44658 44841 44589 5892 38107 52243 10696 194 44022 14009 53824 40674 41169 32329 3475 819 30495 26017 6093 7410 21659 12755 14881 11716 46921 2523 4852 6089 10083 24530 53449 [出力例] 20365.040000000001 |