C++の練習を兼ねて, AtCoder Regular Contest 120 の 問題C (Swaps 2) を解いてみた.
■感想.
1. 問題Cは, 解答方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 個人的には, 問題の背景に, 転倒数の性質が使われている部分が, 非常に面白いと感じた.
3. Binary Indexed Tree の 復習が出来たので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 120 解説 の 各リンク を ご覧下さい.
■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 |
// 解き直し. // https://atcoder.jp/contests/arc120/editorial/1921 // 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 a first #define b second int a[202020], b[202020]; // 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); set<int> aSet, bSet; map<int, int> m; rep(i, N){ scanf("%d", &a[i]); a[i] += (i + 1); aSet.insert(a[i]); m[a[i]]++; } rep(i, N){ scanf("%d", &b[i]); b[i] += (i + 1); bSet.insert(b[i]); } // 2. A, B の 集合を比較. if(aSet != bSet){ puts("-1"); return 0; } // 3. A, B の 値を, 1 ～ N に収まるように変換. int idx = 0; for(auto &p : m) p.b = ++idx; rep(i, N) a[i] = m[a[i]], b[i] = m[b[i]]; // 4. B の それぞれの出現位置を保存. vector<deque<int>> dq(idx + 1); rep(i, N) dq[b[i]].push_back(i + 1); // 5. 転倒数 を 計算. BIT<LL> ft(N + 1); LL ans = 0; rep(i, N){ // 5-1. 数列 a[i] に対する 数列 B の 位置は？ int pos = dq[a[i]].front(); dq[a[i]].pop_front(); // 5-2. 上記の場所に, 1 を 加算. ft.add(pos, 1LL); // 5-3. 区間[pos + 1, N] の 合計は？ LL t = ft.sum(pos + 1, N + 1); // 5-4. 集計. ans += t; } // 6. 出力. 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 |
[入力例] 3 3 1 4 6 2 0 [出力例] 2 ※AtCoderテストケースより [入力例] 3 1 1 1 1 1 2 [出力例] -1 ※AtCoderテストケースより [入力例] 5 5 4 1 3 2 5 4 1 3 2 [出力例] 0 ※AtCoderテストケースより [入力例] 6 8 5 4 7 4 5 10 5 6 7 4 1 [出力例] 7 ※AtCoderテストケースより [入力例] 15 1 1 3 1 9 10 2 3 9 0 3 4 6 2 9 1 1 3 1 4 10 12 3 1 4 3 4 11 2 3 [出力例] 17 [入力例] 100 6 29 11 49 18 34 32 11 31 30 19 7 25 32 48 22 10 6 22 45 20 5 16 27 34 24 46 17 40 27 24 33 39 48 30 33 3 21 41 24 24 4 8 13 9 30 27 3 25 26 17 15 40 10 44 40 16 45 41 43 4 7 20 18 13 10 9 42 26 22 31 42 25 18 4 5 30 10 43 38 44 29 2 36 1 35 29 19 0 4 14 15 10 3 21 4 17 16 18 13 6 12 16 15 18 18 20 19 21 21 27 26 26 25 25 24 23 22 22 21 24 24 23 26 26 25 24 25 25 25 26 25 26 25 28 28 27 27 26 25 24 23 24 24 24 23 22 24 24 23 23 22 23 22 21 20 21 21 21 21 21 20 20 21 21 22 22 24 23 23 23 23 23 23 23 23 23 22 23 23 22 21 22 23 22 21 23 23 24 24 23 22 23 22 22 22 23 23 23 25 [出力例] 696 [入力例] 200 26 55 51 41 20 33 64 21 31 3 21 2 28 47 12 64 19 60 8 12 64 22 30 19 35 36 37 63 24 19 0 33 18 42 34 38 6 57 19 0 63 32 52 57 12 54 66 21 36 29 25 66 18 56 5 39 19 59 59 9 64 0 10 23 26 60 62 22 16 46 20 58 38 12 15 44 8 15 8 54 13 55 0 20 58 62 66 44 61 4 66 49 50 22 56 54 56 26 19 26 41 14 58 13 24 31 17 64 50 48 44 17 18 0 8 21 14 34 26 8 49 18 45 26 64 37 43 19 49 66 2 53 23 20 55 40 35 10 9 8 5 59 61 30 26 66 52 53 62 44 27 23 27 1 32 34 54 31 57 64 3 49 41 33 12 61 63 25 12 42 16 2 15 39 0 43 23 18 31 54 49 39 18 15 11 38 58 42 25 27 63 57 22 66 48 60 51 0 58 59 12 12 22 23 22 21 22 23 34 22 25 27 27 26 26 16 26 26 26 29 39 31 30 30 32 31 31 32 22 31 31 30 31 31 34 33 32 33 32 33 33 32 33 32 31 32 32 32 34 35 34 33 32 32 32 31 33 32 32 31 30 31 31 30 30 29 28 32 32 34 33 38 38 39 39 40 39 38 38 37 37 36 35 36 38 38 37 37 37 36 37 37 36 35 35 35 34 34 34 34 36 35 34 36 36 36 36 35 36 36 36 36 35 34 33 34 33 32 32 32 32 31 31 31 30 30 30 30 30 31 32 32 35 36 35 35 35 34 35 34 34 33 33 33 33 32 33 33 36 37 36 36 36 35 35 34 36 36 37 36 35 35 35 35 34 34 34 33 32 34 33 38 38 37 36 36 35 35 35 35 35 35 36 37 39 38 40 42 41 40 43 51 52 54 54 58 59 59 60 60 [出力例] 1992 |
■参照サイト
AtCoder Regular Contest 120
Binary Indexed Tree (Fenwick Tree)