C++の練習を兼ねて, AtCoder Beginner Contest 100 の 問題D (Patisserie ABC) を解いてみた.
■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考に, AC版に到達できた.
2. 解説にある符号を考慮した全探索で, 最大値を抽出するロジックが, 個人的には, 非常に面白く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 100 解説 を ご覧下さい.
■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/abc100/editorial.pdf // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using vl = vector<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 pb push_back #define all(x) x.begin(), x.end() LL x[1010], y[1010], z[1010]; int main(){ // 1. 入力情報. int N, M; scanf("%d %d", &N, &M); rep(i, N) scanf("%lld %lld %lld", &x[i], &y[i], &z[i]); // 2. 全探索. LL ans = -202020202020202020; rep(i, 1 << 3){ // 2-1. 符号. int s[3]; rep(j, 3) s[j] = (i & (1 << j)) ? 1 : -1; // 2-2. 綺麗さ, おいしさ, 人気度 の (符号付き)合計. vl v; rep(j, N) v.pb(x[j] * s[0] + y[j] * s[1] + z[j] * s[2]); // 2-3. sort. sort(all(v)); // 2-4. 大きい順に, M個. LL t = 0; rep(j, M) t += v[N - 1 - j]; // 2-5. 最大値更新. ans = max(ans, t); } // 3. 出力. 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 |
[入力例] 5 3 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 [出力例] 56 ※AtCoderテストケースより [入力例] 5 3 1 -2 3 -4 5 -6 7 -8 -9 -10 11 -12 13 -14 15 [出力例] 54 ※AtCoderテストケースより [入力例] 10 5 10 -80 21 23 8 38 -94 28 11 -26 -2 18 -69 72 79 -26 -86 -54 -72 -50 59 21 65 -32 40 -94 87 -62 18 82 [出力例] 638 ※AtCoderテストケースより [入力例] 3 2 2000000000 -9000000000 4000000000 7000000000 -5000000000 3000000000 6000000000 -1000000000 8000000000 [出力例] 30000000000 ※AtCoderテストケースより [入力例] 5 3 144 15 -62 51 -54 131 135 -84 33 56 15 -20 -85 121 51 [出力例] 555 [入力例] 10 5 1040 -428 453 145 267 -916 177 664 1270 1111 -1139 800 -666 1125 872 214 -251 1048 663 103 -242 -696 964 108 1095 135 -450 915 193 -719 [出力例] 7777 [入力例] 30 12 2380290 -3874089 2225751 1397296 6482937 -1511776 936588 3280145 -5529143 3729139 798728 -1827712 4073447 -5934867 18870583 1465042 -2344443 1453900 4976600 4863530 1155788 831766 -6177751 6705880 -1387521 6911937 1305672 -2164290 1147022 9051983 -2071730 4990138 1143816 1486505 -8642625 1439353 2296136 -1319424 1215097 950669 1626133 2240346 -9345210 2486543 3900715 1967137 -1407849 1349998 1166523 3341920 2021650 -1377692 -2914269 1199173 1368469 -5705370 1025103 1823988 3869999 -1537211 -6939050 -1096274 -7844622 816106 -1355430 1813427 1202876 -249023 2224158 1120622 -9998050 4192084 -4739977 1249319 -1557077 992298 6869258 -1207735 1746909 1898002 -6951358 1903970 -8996164 1959390 -1541635 8794420 5602718 -4950188 1212287 1628534 [出力例] 123456789 |
■参照サイト
AtCoder Beginner Contest 100