C++の練習を兼ねて, AtCoder Regular Contest 128 の 問題C (Max Dot) を解いてみた.
■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 解説のロジックで, スコアを計算できることに, 非常に興味深い印象を受けた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 128 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題C/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 |
// 解き直し. // https://atcoder.jp/contests/arc128/editorial/2785 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using P = pair<LL, LL>; #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 LL a[5050], aCum[5050]; int main(){ // 1. 入力情報. int N; LL M, S; scanf("%d %lld %lld", &N, &M, &S); rep(i, N) scanf("%lld", &a[i]); // 2. 累積和. rep(i, N) aCum[i + 1] = aCum[i] + a[i]; // 3. 集計. LL a1 = 0; double a2 = 0.0; int r = N; while(r > 0){ // 3-1. sum[i] / i を 最大化する i は? P f = {-1, 1}; int c = 0, m = 0; repr(j, r - 1, 0){ LL d = aCum[r] - aCum[j]; ++c; // 最大値更新. if(c * f.a < d * f.b){ f = {(LL)d, (LL)c}; m = c; } } // 3-2. 集計. // 後ろ m 項 が S / m. if(S <= (LL)m * M){ a2 += (double)((aCum[r] - aCum[r - m]) * S) / (double)m; break; } // 後ろ m 項 が M. if(S > (LL)m * M){ a1 += (aCum[r] - aCum[r - m]) * M; S -= (LL)m * M; } // 3-3. 次へ. r -= m; } // 4. 合算. double ans = (double)a1 + a2; // 5. 出力. 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 |
[入力例] 3 2 3 1 2 3 [出力例] 8.00000000000000000000 ※AtCoderのテストケースより ※但し, 上記のプログラムでは, 以下の内容が出力される. 8.000000000000 [入力例] 3 3 2 5 1 1 [出力例] 4.66666666666666666667 ※AtCoderのテストケースより ※但し, 上記のプログラムでは, 以下の内容が出力される. 4.666666666667 [入力例] 10 234567 1000000 353239 53676 45485 617014 886590 423581 172670 928532 312338 981241 [出力例] 676780145098.25000000000000000000 ※AtCoderのテストケースより ※但し, 上記のプログラムでは, 以下の内容が出力される. 676780145098.250000000000 [入力例] 5 7 9 3 1 4 1 5 [出力例] 40.000000000000 [入力例] 10 7 11 5 1 8 2 5 1 1 2 3 1 [出力例] 31.900000000000 [入力例] 30 7 32 12 10 47 31 61 78 56 110 93 35 49 20 105 81 118 70 38 100 53 96 111 39 125 75 14 82 102 11 121 112 [出力例] 3003.500000000000 [入力例] 77 11 23 500 491 151 557 745 448 1107 591 870 1196 204 206 559 1014 349 588 95 181 627 1228 559 618 659 870 476 126 737 706 578 910 1105 1108 563 926 388 947 479 920 7 996 985 339 113 429 782 322 782 646 996 73 705 1208 840 369 449 709 732 401 784 1053 546 1023 697 497 1008 166 1026 500 1010 99 10 11 222 111 333 777 666 [出力例] 16495.964912280702 |