C++の練習を兼ねて, AtCoder Beginner Contest 261 の 問題F (Sorting Color Balls) を解いてみた.
■感想.
1. 問題Fは, 方針が見えなかったので, 解説を参考にして, ようやく, AC版に到達出来た.
2. Binary Indexed Tree (転倒数) の 復習が出来たので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 261 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題F／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 |
// 解き直し. // https://atcoder.jp/contests/abc261/editorial/4484 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using vi = vector<int>; using vvi = vector<vi>; #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 a first #define b second #define pb push_back int c[303030], x[303030]; // Binary Indexed Tree (Fenwick Tree) // https://youtu.be/lyHk98daDJo?t=7960 template<typename T> struct BIT{ int n; vector<T> d; BIT(int n = 0) : n(n), d(n + 1) {} void add(int i, T x = 1){ for(i++; i <= n; i += i & -i) d[i] += x; } T sum(int i){ T x = 0; for(i++; i; i -= i & -i) x += d[i]; return x; } T sum(int l, int r){ return sum(r - 1) - sum(l - 1); } }; int main(){ // 1. 入力情報. int N; scanf("%d", &N); map<int, int> m; rep(i, N){ scanf("%d", &c[i]); m[c[i]] = 0; } rep(i, N) scanf("%d", &x[i]); // 2. 転倒数(M[0]) を 計算. BIT<LL> ft0(N + 1); LL ans = 0; rep(i, N){ // 2-1. 位置 x[i] に, 1 を 加算. ft0.add(x[i], 1LL); // 2-2. 区間[x[i] + 1, N] の 合計は？ LL t = ft0.sum(x[i] + 1, N + 1); // 2-3. 集計. ans += t; } // 3. 事前準備. // 3-1. 座標圧縮(球の色). int idx = -1; for(auto &p : m) p.b = ++idx; // 3-2. 球の色ごとに, 整数 X[i] を 分類し, 座標圧縮も行う. vvi tx(idx + 1), cx(idx + 1); rep(i, N) tx[m[c[i]]].pb(x[i]); rep(i, idx + 1){ map<int, int> n; rep(j, tx[i].size()) n[tx[i][j]] = 0; int jdx = 0; for(auto &p : n) p.b = ++jdx; rep(j, tx[i].size()) cx[i].pb(n[tx[i][j]]); } // 4. 転倒数(M[k]) を 計算. rep(i, idx + 1){ int n = cx[i].size(); BIT<LL> ftk(n + 1); rep(j, n){ // 4-1. 位置 cx[i][j] に, 1 を 加算. ftk.add(cx[i][j], 1LL); // 4-2. 区間[cx[i][j] + 1, n] の 合計は？ LL t = ftk.sum(cx[i][j] + 1, n + 1); // 4-3. 集計(減算). ans -= t; } } // 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 |
[入力例] 5 1 5 2 2 1 3 2 1 2 1 [出力例] 6 ※AtCoderテストケースより [入力例] 3 1 1 1 3 2 1 [出力例] 0 ※AtCoderテストケースより [入力例] 3 3 1 2 1 1 2 [出力例] 0 ※AtCoderテストケースより [入力例] 8 1 3 2 1 1 1 2 3 3 2 1 3 1 2 2 1 [出力例] 10 [入力例] 12 3 1 11 7 7 5 1 3 6 5 6 5 3 2 9 6 9 6 6 8 5 3 7 8 [出力例] 25 [入力例] 30 3 13 6 12 2 13 6 8 7 4 12 3 7 5 5 2 7 8 9 10 3 10 6 7 1 12 10 5 9 1 19 4 10 28 26 9 22 27 11 22 24 5 3 22 17 14 23 10 19 20 22 6 6 6 7 14 27 11 30 20 [出力例] 199 [入力例] 50 11 10 7 9 13 2 1 1 11 11 8 3 9 3 8 12 13 12 7 6 6 3 9 12 1 12 13 15 3 10 9 7 1 7 11 15 12 15 13 3 11 10 3 12 6 11 1 12 2 8 7 8 20 18 17 7 6 38 50 27 35 23 40 33 7 17 7 29 28 19 6 37 27 49 45 7 43 21 17 43 27 17 50 13 11 49 10 26 2 49 27 1 15 13 13 19 16 20 8 2 [出力例] 596 [入力例] 200 18 30 2 35 9 32 57 35 57 50 17 37 3 37 27 38 27 11 39 58 17 23 35 38 36 37 12 2 7 36 19 15 15 58 39 17 19 7 22 15 5 50 18 23 23 58 8 13 10 36 15 23 58 20 1 55 13 23 7 38 55 27 38 35 23 52 22 25 17 30 19 2 32 8 25 9 1 22 16 31 9 28 13 19 50 15 55 16 38 25 5 51 33 7 16 1 55 12 53 55 18 5 21 5 21 50 50 35 52 20 10 18 12 17 25 39 31 26 30 31 29 55 55 55 12 5 9 39 1 9 5 9 38 23 5 58 15 55 26 30 17 18 36 8 26 55 58 13 8 21 15 27 7 11 2 3 50 19 5 8 10 36 31 22 22 55 55 50 55 26 30 12 20 7 6 39 6 39 59 20 19 37 2 21 57 34 6 31 23 22 65 55 33 32 28 2 39 51 5 33 62 186 151 183 31 167 123 136 101 57 130 145 53 98 116 112 28 61 86 152 158 102 29 178 125 33 159 137 56 122 78 33 114 129 161 89 51 68 3 65 173 123 107 135 116 86 50 56 196 66 81 86 143 52 186 189 160 157 177 197 193 193 139 55 106 155 140 18 71 28 17 35 22 60 57 147 34 53 175 177 105 51 156 156 73 138 19 96 96 191 143 102 116 59 22 171 115 115 95 67 93 151 101 183 12 51 171 62 57 158 73 55 36 102 90 20 129 19 148 23 55 189 118 99 96 95 23 85 16 185 170 55 117 162 6 166 145 174 125 15 2 168 151 157 182 151 184 168 9 189 85 95 1 164 165 186 125 75 125 86 159 36 169 55 122 30 110 157 123 136 167 43 36 105 72 124 109 165 128 130 170 197 125 58 55 171 143 166 67 19 133 103 151 27 5 186 139 38 136 189 [出力例] 9393 |
■参照サイト
AtCoder Beginner Contest 261