C++の練習を兼ねて, AtCoder Beginner Contest 076 の 問題D (AtCoder Express) を解いてみた.
■感想.
1. 問題D は, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 解説のロジックで, 走れる最大の距離を計算できることに非常に興味深く思った.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 076 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題D／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 |
// 解き直し. // https://img.atcoder.jp/abc076/editorial.pdf // C++(GCC 9.2.1) #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 t[202], v[202], tCum[202]; double f[40404]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N) scanf("%d", &t[i + 1]); rep(i, N) scanf("%d", &v[i + 1]); // 2. 累積和. rep(i, N + 2) tCum[i + 1] = tCum[i] + t[i]; // 3. 最小速度(0.5秒刻み). rep(i, 40404) f[i] = 2020202020.0; rep(i, N + 2){ // 区間 の l, r. int l = 2 * tCum[i + 0]; int r = 2 * tCum[i + 1]; // 区間[0, l]. repr(x, l, 0) f[x] = min(f[x], (double)v[i] + 0.5 * (l - x)); // 区間[l, r]. repx(x, l, r + 1) f[x] = min(f[x], (double)v[i]); // 区間[r, 40404). repx(x, r, 40404) f[x] = min(f[x], (double)v[i] + 0.5 * (x - r)); } // 4. 集計. double ans = 0.0; rep(x, 2 * tCum[N + 1]) ans += f[x]; // 5. 出力. printf("%.15lf\n", ans / 2); 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 |
[入力例] 1 100 30 [出力例] 2100.000000000000000 ※AtCoderテストケースより [入力例] 2 60 50 34 38 [出力例] 2632.000000000000000 ※AtCoderテストケースより [入力例] 3 12 14 2 6 2 7 [出力例] 76.000000000000000 ※AtCoderテストケースより [入力例] 1 9 10 [出力例] 20.250000000000000000 ※AtCoderテストケースより ※但し, 上記のプログラムでは, 以下の内容が出力される. 20.250000000000000 [入力例] 10 64 55 27 35 76 119 7 18 49 100 29 19 31 39 27 48 41 87 55 70 [出力例] 20291.000000000000 ※AtCoderテストケースより ※但し, 上記のプログラムでは, 以下の内容が出力される. 20291.000000000000000 [入力例] 5 13 152 63 71 93 36 30 22 5 23 [出力例] 7777.000000000000000 [入力例] 30 151 100 66 148 150 40 132 172 164 76 160 121 51 67 39 136 170 133 78 135 125 197 117 151 186 136 111 123 101 92 62 80 50 51 60 77 38 78 86 81 68 77 99 80 79 50 72 52 81 56 87 55 30 33 81 60 62 87 50 64 [出力例] 222222.000000000000000 [入力例] 100 8 121 6 60 172 83 136 108 1 51 165 36 98 164 50 92 66 174 22 175 106 190 110 107 108 38 70 5 93 199 133 119 166 167 68 128 77 66 133 177 87 184 194 34 175 98 153 71 72 119 172 71 51 13 168 156 165 155 31 189 134 127 103 22 67 110 47 25 115 111 49 12 6 39 79 55 128 176 156 184 67 123 167 78 161 184 155 88 76 109 132 59 50 160 122 29 132 110 61 180 5 53 25 54 18 99 19 87 25 8 8 73 26 83 8 26 64 66 59 63 64 33 89 64 57 62 69 50 62 51 60 82 70 33 73 55 99 55 33 62 88 27 87 11 60 86 1 86 96 97 72 63 99 33 11 50 95 60 67 86 55 88 77 64 69 77 79 55 99 7 71 30 94 67 81 23 5 84 31 96 22 55 57 60 70 40 36 51 77 37 57 7 11 58 10 11 89 11 93 58 [出力例] 500000.000000000000000 |
■参照サイト
AtCoder Beginner Contest 076