C++の練習を兼ねて, AtCoder Regular Contest 053 の 問題C (魔法使い高橋君) を解いてみた.
■感想.
1. 方針が見えない部分があったので, 解説を参照したところ, AC版に到達できた.
2. sort対象が, a – b の 正負に応じて, 切り替わる点が, 非常に不思議な感じがして面白く感じた.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトAtCoder Regular Contest 053 解説をご覧下さい.
■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 |
// 解き直し. // https://img.atcoder.jp/data/arc/053/editorial.pdf // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using T3 = tuple<LL, 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 all(x) x.begin(), x.end() int main(){ // 1. 入力情報. int N; scanf("%d", &N); vector<T3> vPos, vNeg; rep(i, N){ LL a, b, c; scanf("%lld %lld", &a, &b); c = a - b; if(c < 0) vNeg.emplace_back(a, b, c); else vPos.emplace_back(a, b, c); } // 2. sort. // https://www.geeksforgeeks.org/sorting-vector-tuple-c-ascending-order/ sort(all(vNeg), [](const T3 &a, const T3 &b){ return get<0>(a) < get<0>(b); }); // for(auto &p : vNeg) printf("a=%lld b=%lld c=%lld\n", get<0>(p), get<1>(p), get<2>(p)); // 3. sort. // https://www.geeksforgeeks.org/sorting-vector-tuple-c-ascending-order/ sort(all(vPos), [](const T3 &a, const T3 &b){ // return get<0>(a) > get<0>(b); // ロジック修正: 解説にある通り, b[i] を 降順sortするのが正しいとのこと. return get<1>(a) > get<1>(b); }); // for(auto &p : vPos) printf("a=%lld b=%lld c=%lld\n", get<0>(p), get<1>(p), get<2>(p)); // 4. 気温の最大値 X を 計算. LL ans = -202020202020202020, X = 0; for(auto &p : vNeg){ X += get<0>(p); ans = max(ans, X); X -= get<1>(p); } for(auto &p : vPos){ X += get<0>(p); ans = max(ans, X); X -= get<1>(p); } // 5. 出力. 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 114 115 116 117 118 119 120 |
[入力例] 1 10 20 [出力例] 10 ※AtCoderのテストケースより [入力例] 2 30 20 10 20 [出力例] 20 ※AtCoderのテストケースより [入力例] 5 5 10 10 5 10 15 15 10 20 20 [出力例] 10 ※AtCoderのテストケースより [入力例] 30 2584211 79319034 105682679 99008547 68923866 64072311 39878833 55875856 22572957 97659203 74863460 24009217 77342946 112684425 14569588 113202108 69907472 67983910 17973818 46844364 66203426 106604582 52903263 57134512 76502220 38251023 15216113 68464096 81635075 6610403 1713679 44027673 36711629 105648520 45643081 36038269 1552992 97196163 9193532 48890284 73582182 101788895 45479724 59781571 33041379 89752152 69425663 15899300 71234115 14814156 113313584 109246472 13384228 7504136 94026442 83782407 22447954 37623640 17225387 38244889 [出力例] 1552992 [入力例] 50 160737 49748 42120 17095 145272 175669 153418 50326 126005 1654 145687 27952 119759 137408 191582 159810 36503 22055 20355 61699 123365 125865 89014 198800 21813 145531 44036 52132 82786 36771 110913 170470 122156 52045 18645 45641 152861 130410 84812 8416 194509 147692 64731 157011 48181 3142 104403 29766 29213 57918 21680 118313 168747 12149 92425 23006 44400 122727 23350 28895 128981 81384 27103 134077 145262 96753 8340 102961 133400 65416 152296 33888 83930 55995 28090 141822 62781 16863 51095 201406 163808 15904 15413 47524 159988 159048 157146 173681 162013 31737 117703 166679 191059 54743 81178 165991 76343 81148 51474 128303 [出力例] 457096 |
■参照サイト
AtCoder Regular Contest 053