C++の練習を兼ねて, AtCoder Beginner Contest 231 の 問題F (Jealous Two) を解いてみた.
■感想.
1. 問題Fは, 実装方針を絞り込めたので, AC版に到達出来たと思う.
2. Binary Indexed Tree の 復習が出来たので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 231 解説 を ご覧下さい.
■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 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using vi = vector<int>; using P = pair<int, int>; #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 #define all(x) x.begin(), x.end() // 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); } }; struct joy{ int a, b; bool operator < (const joy &J) const{ return (a > J.a) || (a == J.a && b < J.b); } }; int main(){ // 1. 入力情報. int N; scanf("%d", &N); vi A(N), B(N); map<int, int> m; rep(i, N) scanf("%d", &A[i]); rep(i, N){ scanf("%d", &B[i]); m[B[i]] = 1; } // 2. 同一要素の出現を考慮する必要がある？ map<P, int> mo; rep(i, N) mo[{A[i], B[i]}]++; LL ans = 0; for(auto &p : mo) ans += (LL)(p.b - 1) * (LL)p.b / 2; // 3. 座標圧縮(青木君の嬉しさ). int idx = 0; for(auto &p : m) p.b = ++idx; // 4. 累積和. vi bCum(idx + 1); rep(i, N) bCum[m[B[i]]]++; rep(i, idx) bCum[i + 1] += bCum[i]; // 5. sort; vector<joy> v; rep(i, N) v.emplace_back(joy{A[i], B[i]}); sort(all(v)); // 6. 集計(i番目以降の青木君の嬉しさが, i番目の青木君の嬉しさ以上のものをカウントしたい). BIT<int> ft(idx + 1); rep(i, N){ // 青木君 の 嬉しさ(BIT の 加算位置). int j = m[v[i].b]; // 今回までで, 嬉しさ j以上 が, 何回出現したか？ // -> 区間[j, idx + 1) の 合計は？ int bCount = ft.sum(j, idx + 1); // 嬉しさ j以上 の 出現回数合計. int cCount = bCum[idx] - bCum[j - 1]; // 次回以降で, j以上の嬉しさが, 何回出現できるか？ ans += (LL)(cCount - bCount); // 出現回数 として 加算. ft.add(j, 1); } // 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 |
[入力例] 3 50 100 150 1 3 2 [出力例] 4 ※AtCoderテストケースより [入力例] 3 123456789 123456 123 987 987654 987654321 [出力例] 6 ※AtCoderテストケースより [入力例] 10 3 1 4 1 5 9 2 6 5 3 2 7 1 8 2 8 1 8 2 8 [出力例] 37 ※AtCoderテストケースより [入力例] 5 5 9 7 3 7 0 6 1 2 1 [出力例] 10 [入力例] 25 1 83 57 35 11 80 87 64 91 89 2 7 56 64 7 10 83 11 2 7 64 45 64 83 55 8 97 61 39 11 85 34 21 72 88 2 7 34 21 7 15 50 11 2 7 16 61 21 97 65 [出力例] 99 [入力例] 100 54 15 84 28 42 95 87 62 81 6 44 70 58 65 92 11 10 92 40 20 33 62 64 18 64 3 15 93 52 93 71 72 27 23 79 25 9 15 55 94 0 97 46 56 20 51 24 77 4 37 55 57 90 48 53 25 74 7 76 45 60 90 30 42 84 87 25 23 0 48 62 5 88 34 77 81 17 60 88 5 15 65 13 71 45 0 15 71 63 79 2 38 76 53 91 94 18 22 36 89 56 34 20 1 66 99 72 87 78 39 83 97 26 48 88 41 49 56 24 11 87 26 63 62 65 99 19 13 99 12 34 13 37 24 53 91 3 18 15 18 62 73 56 63 46 97 62 97 66 77 90 24 19 62 25 50 24 12 49 14 33 94 79 47 78 86 3 95 16 3 99 77 18 62 22 16 60 92 49 63 53 37 19 88 28 36 26 92 54 4 12 19 30 52 19 76 98 96 27 71 [出力例] 2500 |
■参照サイト
パナソニックプログラミングコンテスト2021(AtCoder Beginner Contest 231)
Binary Indexed Tree (Fenwick Tree)