C++の練習を兼ねて, AtCoder Grand Contest 018 の 問題C (Coins) を解いてみた.
■感想.
1. 問題Cは, 解答方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 解答に至るまでの実装方針が, 個人的には, 非常に不思議な印象を受ける面白い問題に感じた.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Grand Contest 018 解説 を ご覧下さい.
■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 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 132 133 134 135 136 137 138 139 140 |
// 解き直し. // https://img.atcoder.jp/agc018/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--) #define pb push_back #define all(x) x.begin(), x.end() LL cum[101010][3]; // 金, 銀, 銅 の 枚数 の 累積和. LL lCoin[101010], rCoin[101010]; struct Coin{ LL a, b, c, d; // 金, 銀, 銅, 差分. bool operator < (const Coin& rhs) const{ return d > rhs.d; } }; int main(){ // 1. 入力情報. int X, Y, Z, A = 0; scanf("%d %d %d", &X, &Y, &Z); vector<Coin> v; A = X + Y + Z; rep(i, A){ Coin c; scanf("%lld %lld %lld", &c.a, &c.b, &c.c); c.d = c.a - c.b; v.pb(c); } // 2. sort(金コイン枚数 - 銀コイン枚数). sort(all(v)); reverse(all(v)); // for(auto &p : v) printf("a=%lld b=%lld c=%lld d=%lld\n", p.a, p.b, p.c, p.d); // 3. 累計和. rep(i, A){ cum[i + 1][0] = cum[i][0] + v[i].a; // 金. cum[i + 1][1] = cum[i][1] + v[i].b; // 銀. cum[i + 1][2] = cum[i][2] + v[i].c; // 銅. } // 4. 左側から貰う 銀コイン, 銅コイン の 和 を 計算. // 4-1. 初期化. LL gold, silver, bronze; priority_queue<Coin> pq; silver = cum[Y][1]; bronze = 0; lCoin[Y] = silver + bronze; rep(i, Y){ Coin c; c.a = v[i].a; c.b = v[i].b; c.c = v[i].c; c.d = c.b - c.c; // 銀コイン枚数 - 銅コイン枚数. pq.push(c); } // 4-2. K = Y ~ X + Y + Z で 確認. repx(i, Y, A){ // コイン情報を取得. Coin c = v[i]; // 銀コインの枚数を更新. silver += c.b; // コイン情報を保存. c.d = c.b - c.c; pq.push(c); // コイン情報を取り出す. c = pq.top(); pq.pop(); // 銀, 銅コインの枚数を更新. silver -= c.b; bronze += c.c; // コインの合計枚数を保存. lCoin[i + 1] = silver + bronze; } // 5. 右側から貰う 金コイン, 銅コイン の 和 を 計算. // 5-1. 初期化. pq = priority_queue<Coin>(); gold = cum[A][0] - cum[A - X][0]; bronze = 0; rCoin[A - X] = gold + bronze; repr(i, A - 1, A - X){ Coin c; c.a = v[i].a; c.b = v[i].b; c.c = v[i].c; c.d = c.a - c.c; // 金コイン枚数 - 銅コイン枚数. pq.push(c); } // 5-2. K = Y + Z ~ 0 で 確認. repr(i, A - X - 1, 0){ // コイン情報を取得. Coin c = v[i]; // 金コインの枚数を更新. gold += c.a; // コイン情報を保存. c.d = c.a - c.c; pq.push(c); // コイン情報を取り出す. c = pq.top(); pq.pop(); // 金, 銅コインの枚数を更新. gold -= c.a; bronze += c.c; // コインの合計枚数を保存. rCoin[i] = gold + bronze; } // 6. 最大値を計算. LL ans = 0; repx(i, Y, A - X + 1) ans = max(ans, lCoin[i] + rCoin[i]); // rep(i, A + 1) printf("%lld ", lCoin[i]); // puts(""); // rep(i, A + 1) printf("%lld ", rCoin[i]); // puts(""); // 7. 出力. 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 |
[入力例] 1 2 1 2 4 4 3 2 1 7 6 7 5 2 3 [出力例] 18 ※AtCoderテストケースより [入力例] 3 3 2 16 17 1 2 7 5 2 16 12 17 7 7 13 2 10 12 18 3 16 15 19 5 6 2 [出力例] 110 ※AtCoderテストケースより [入力例] 6 2 4 33189 87907 277349742 71616 46764 575306520 8801 53151 327161251 58589 4337 796697686 66854 17565 289910583 50598 35195 478112689 13919 88414 103962455 7953 69657 699253752 44255 98144 468443709 2332 42580 752437097 39752 19060 845062869 60126 74101 382963164 [出力例] 3093929975 ※AtCoderテストケースより [入力例] 5 4 3 11 6 1 12 7 2 13 8 3 19 15 11 20 16 12 10 4 7 11 5 8 12 6 9 23 20 18 15 13 21 18 19 10 30 31 22 [出力例] 189 [入力例] 12 11 10 112 46 40 61 35 96 41 115 24 55 101 118 12 81 70 114 118 25 84 30 5 102 91 21 59 24 85 93 4 50 76 8 83 75 68 76 73 16 104 120 100 39 22 21 27 27 55 29 29 37 23 72 89 25 21 45 75 99 23 49 102 110 43 53 19 106 120 67 8 61 31 65 76 62 58 80 107 115 81 6 51 32 110 76 97 86 111 46 101 8 46 116 93 27 18 69 40 61 19 [出力例] 3000 |
■参照サイト
AtCoder Grand Contest 018