C++の練習を兼ねて, AtCoder Regular Contest 096 の 問題D (Static Sushi)を解いてみた.
■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考に実装して, AC版に到達できたので, 良かったと思う.
2. 実装に苦労したものの, 個人的には, 非常に面白い問題に感じた.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Regular Contest 096 解説 を ご覧下さい.
■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 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 |
// 解き直し. // https://img.atcoder.jp/arc096/editorial.pdf // 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], v[101010]; LL fab[101010], gab[101010], hab[101010]; // O -> A -> B の 場合. LL fba[101010], gba[101010], hba[101010]; // O -> B -> A の 場合. int main(){ // 1. 入力情報. int N; LL C; scanf("%d %lld", &N, &C); rep(i, N) scanf("%lld %lld", &x[i + 1], &v[i + 1]); // 2. 累積和. // 2-1. O -> A -> B の ケース. // ex. // x[b] = x[0] ～ x[3] で 考える. // x[0] -> fab[0] = v[3] + v[2] + v[1] - (C - x[1]) // hab[0] = 0 // // x[1] -> fab[1] = v[3] + v[2] - (C - x[2]) // hab[1] = v[1] - 2 * x[1] // // x[2] -> fab[2] = v[3] - (C - x[3]) // hab[2] = v[1] + v[2] - 2 * x[2] // // x[3] -> fab[3] = 0 // hab[3] = v[1] + v[2] + v[3] - 2 * x[3] fab[N - 1] = v[N] - (C - x[N]); repr(i, N - 2, 0) fab[i] = fab[i + 1] - x[i + 2] + v[i + 1] + x[i + 1]; repr(i, N - 1, 0) gab[i] = max(gab[i + 1], fab[i]); repx(i, 1, N + 1) hab[i] = hab[i - 1] + v[i] + 2 * x[i - 1] - 2 * x[i]; // 2-2. O -> B -> A の ケース. // ex. // x[b] = x[1] ～ x[4] で 考える. // x[1] -> fba[1] = 0. // hba[1] = v[3] + v[2] + v[1] - 2 * (C - x[1]) // // x[2] -> fba[2] = v[1] - x[1] // hba[2] = v[3] + v[2] - 2 * (C - x[2]) // // x[3] -> fba[3] = v[1] + v[2] - x[2] // hba[3] = v[3] - 2 * (C - x[3]) // // x[4] -> fba[4] = v[1] + v[2] + v[3] - x[3] // hba[4] = 0 repx(i, 1, N + 1) fba[i + 1] = fba[i] + x[i - 1] + v[i] - x[i]; repx(i, 1, N + 1) gba[i + 1] = max(gba[i], fba[i + 1]); hba[N] = v[N] - 2 * (C - x[N]); repr(i, N - 1, 1) hba[i] = hba[i + 1] + v[i] - 2 * x[i + 1] + 2 * x[i]; // 3. 最適解を調査. // 3-1. O -> A -> B の ケース. LL maxAB = 0; rep(i, N + 1) maxAB = max(maxAB, gab[i] + hab[i]); // 3-2. O -> B -> A の ケース. LL maxBA = 0; repx(i, 1, N + 2) maxBA = max(maxBA, gba[i] + hba[i]); // 4. 出力. printf("%lld\n", max(maxAB, maxBA)); 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 |
[入力例] 3 20 2 80 9 120 16 1 [出力例] 191 ※AtCoderテストケースより [入力例] 3 20 2 80 9 1 16 120 [出力例] 192 ※AtCoderテストケースより [入力例] 1 100000000000000 50000000000000 1 [出力例] 0 ※AtCoderテストケースより [入力例] 15 10000000000 400000000 1000000000 800000000 1000000000 1900000000 1000000000 2400000000 1000000000 2900000000 1000000000 3300000000 1000000000 3700000000 1000000000 3800000000 1000000000 4000000000 1000000000 4100000000 1000000000 5200000000 1000000000 6600000000 1000000000 8000000000 1000000000 9300000000 1000000000 9700000000 1000000000 [出力例] 6500000000 ※AtCoderテストケースより [入力例] 20 12345 216 1953 805 1387 1024 339 1235 1775 2263 447 2880 1280 2911 1812 3727 1327 4195 635 5035 934 5906 181 7096 252 7112 1620 7420 1247 7482 499 8695 236 8753 741 9619 1376 10489 891 11945 921 [出力例] 8564 [入力例] 50 43210 237 993 1591 2415 2013 6797 2575 2596 3223 7909 4435 3930 5521 4623 7927 959 8633 11508 9242 3343 9609 1694 10226 11182 10968 3342 11387 1321 11811 5863 13076 127 13720 3326 14389 11454 14587 4676 14689 8252 17108 4772 18778 1438 19206 8289 19244 10069 20159 12154 21251 2894 21346 12149 21526 7212 22168 5054 22841 5789 22937 1035 23196 10093 23806 1083 23969 5864 26460 10453 27707 5279 28000 9671 31441 5411 31974 7757 32080 5297 33436 5386 33661 2841 34755 10657 35265 8111 35730 7977 37155 10930 39539 5982 40436 1757 41385 5137 43151 10802 [出力例] 256150 |
■参照サイト
AtCoder Regular Contest 096