C++の練習を兼ねて, AtCoder Regular Contest 100 の 問題E (Or Plus Max) を解いてみた.
■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考にして, ようやく, AC版に到達出来た.
2. 問題Eで, 高速ゼータ変換に関する考え方に触れることが出来たので, 非常に良かったと思う.
3. 実装に苦労したものの, 個人的には, 上位二個の要素を更新していくロジックが, 非常に面白いと感じた.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 100 解説 を ご覧下さい.
■C++版プログラム(問題E／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 |
// 解き直し. // https://img.atcoder.jp/arc100/editorial.pdf // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using P = pair<int, int>; using PQ = priority_queue<P>; using vp = vector<P>; #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 a first #define b second #define all(x) x.begin(), x.end() P a[303030]; PQ pq[303030]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, 1 << N){ int t; scanf("%d", &t); a[i].a = t; a[i].b = i; pq[i].push(a[i]); } // 2. 上位二桁更新. rep(i, 1 << N){ rep(j, N){ // 2-1. j ビット目が, 1 の 場合は, 更新対象外. int bit = 1 << j; if(i & bit) continue; // 2-2. 更新対称 の 位置 を 取得. int ni = i + bit; // 2-3. ni 番目 の 要素 に, i番目 の 要素を全て追加. // -> i 番目 の 要素 を コピーしてから実施. PQ cPQ = pq[i]; while(!cPQ.empty()){ P u = cPQ.top(); cPQ.pop(); pq[ni].push(u); } // 2-4. 重複要素削除. // -> i 番目 の 要素 を 追加すると, ダブルカウントしている場合があるので, 重複削除. set<P> st; while(!pq[ni].empty()){ P u = pq[ni].top(); pq[ni].pop(); st.insert(u); } // 2-5. ni 番目の要素数が, 二個になるように調整. while(!pq[ni].empty()) pq[ni].pop(); vp v; for(auto &p : st) v.pb(p); reverse(all(v)); assert(v.size() >= 2); pq[ni].push(v[0]); pq[ni].push(v[1]); } } // 3. 累積max ～ 出力. int ans = 0; repx(i, 1, 1 << N){ // 3-1. i番目の要素を取得. int t = pq[i].top().a; pq[i].pop(); t += pq[i].top().a; // 3-2. 累積max更新. ans = max(ans, t); // 3-3. 出力. printf("%d\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 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 |
[入力例] 2 1 2 3 1 [出力例] 3 4 5 ※AtCoderテストケースより [入力例] 3 10 71 84 33 6 47 23 25 [出力例] 81 94 155 155 155 155 155 ※AtCoderテストケースより [入力例] 4 75 26 45 72 81 47 97 97 2 2 25 82 84 17 56 32 [出力例] 101 120 147 156 156 178 194 194 194 194 194 194 194 194 194 ※AtCoderテストケースより [入力例] 5 96 64 33 40 80 30 121 72 93 15 1 65 75 16 8 80 118 52 51 2 84 7 100 75 116 122 64 16 29 31 80 50 [出力例] 160 160 160 176 176 217 217 217 217 217 217 217 217 217 217 217 217 217 217 217 217 239 239 239 240 240 240 240 240 240 243 [入力例] 6 801 583 932 1190 85 653 62 420 598 31 896 1153 1127 1203 780 664 283 325 1079 74 702 1123 188 263 136 216 591 3 1232 699 510 1032 1154 694 59 362 804 527 73 997 150 1196 1076 1036 999 633 438 1055 349 549 277 197 1078 608 155 606 864 516 158 653 1073 393 1002 306 [出力例] 1384 1733 2122 2122 2122 2122 2122 2122 2122 2122 2343 2343 2343 2343 2393 2393 2393 2393 2393 2393 2393 2393 2393 2393 2393 2393 2393 2393 2435 2435 2435 2435 2435 2435 2435 2435 2435 2435 2435 2435 2435 2435 2435 2435 2435 2435 2435 2435 2435 2435 2435 2435 2435 2435 2435 2435 2435 2435 2435 2435 2435 2435 2435 |
■参照サイト
AtCoder Regular Contest 100