C++の練習を兼ねて, AtCoder Beginner Contest 190 の 問題F (Shift and Inversions)を解いてみた.
■感想.
1. 問題Fは, 方針が見えなかったので, 解説を見て提出したところ, AC版に到達できたので, 良かったと思う.
2. Binary Indexed Tree の 復習が出来たので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Beginner Contest 190 解説 の 各リンク を ご覧下さい.
■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 |
// 解き直し. // https://atcoder.jp/contests/abc190/editorial/631 // 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--) LL a[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); rep(i, N) scanf("%lld", &a[i]); // 2. 転倒数(数列 A) を 計算. BIT<LL> ft(N + 1); LL per = 0; rep(i, N){ // 2-1. 位置 a[i] に, 1 を 加算. ft.add(a[i], 1LL); // 2-2. 区間[a[i] + 1, N] の 合計は？ LL t = ft.sum(a[i] + 1, N + 1); // 2-3. 集計. per += t; } // 3. 転倒数(数列 B) を 計算しながら出力. LL ans = per; rep(i, N){ // 3-1. 出力. printf("%lld\n", ans); // 3-2. 差分更新(※解説通り). ans += (LL)(N - 1 - 2 * a[i]); } 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 |
[入力例] 4 0 1 2 3 [出力例] 0 3 4 3 ※AtCoderテストケースより [入力例] 10 0 3 1 5 4 2 9 6 8 7 [出力例] 9 18 21 28 27 28 33 24 21 14 ※AtCoderテストケースより [入力例] 20 16 7 4 13 9 10 5 6 17 11 19 3 2 8 1 18 15 14 0 12 [出力例] 100 87 92 103 96 97 96 105 112 97 94 75 88 103 106 123 106 95 86 105 [入力例] 50 31 17 46 41 23 13 6 3 38 24 37 20 39 48 30 7 29 1 12 10 11 22 21 47 8 45 16 32 34 43 27 19 33 15 9 44 4 14 18 25 28 42 2 5 36 40 49 26 35 0 [出力例] 621 608 623 580 547 550 573 610 653 626 627 602 611 582 535 524 559 550 597 622 651 678 683 690 645 678 637 654 639 620 583 578 589 572 591 622 583 624 645 658 657 650 615 660 699 676 645 596 593 572 |
■参照サイト
AtCoder Beginner Contest 190
Binary Indexed Tree (Fenwick Tree)