C++の練習を兼ねて, AtCoder Regular Contest 043 の 問題C (転倒距離) を解いてみた.
■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考にして, ようやく, AC版に到達出来た.
2. Binary Indexed Tree (転倒数) の 復習が出来たので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 043 解説 を ご覧下さい.
■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 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 |
// 解き直し. // https://www.slideshare.net/chokudai/arc043 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using vi = vector<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 pb push_back const int MAX = 101010; int ia[MAX], oa[MAX], ib[MAX], ob[MAX], a[MAX], b[MAX], tc[MAX], ic[MAX], oc[MAX], ca[MAX], cb[MAX]; LL f[MAX]; // 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); repx(i, 1, N + 1){ scanf("%d", &ia[i]); oa[ia[i]] = i; } repx(i, 1, N + 1){ scanf("%d", &ib[i]); ob[ib[i]] = i; } // 2. 順列 B の 並べ替え. repx(i, 1, N + 1) a[i] = i; repx(i, 1, N + 1) b[i] = oa[ib[i]]; // 3. 順列 A, B との 転倒距離は? // -> フラグも保存する. LL T = 0; BIT<LL> ft(N + 2); repx(i, 1, N + 1){ // 位置 b[i] に, 加算. ft.add(b[i], 1); // 区間[b[i] + 1, N + 1) の 合計は? f[b[i]] = ft.sum(b[i] + 1, N + 1); // 集計. T += f[b[i]]; } // 4. 例外. if(T & 1){ puts("-1"); return 0; } // 5. 順列 C の 候補は? LL U = T / 2; repx(i, 1, N + 1){ // 残り(バブルソート). if(f[i] > U){ // 整数 i を, U 回 前方 に 移動. int at = -1; vi v; repx(j, 1, N + 1){ if(b[j] >= i) v.pb(b[j]); if(b[j] == i) at = v.size(); } // バブルソート(U 回). repr(j, at - 1, at - (int)U) swap(v[j], v[j - 1]); // 移し替え. repx(j, i, N + 1) tc[j] = v[j - i]; // 終了. break; } // Skip(バブルソートのシュミレート). tc[i] = i; U -= f[i]; } // 6. 順列 C は? // -> 順列 A を 1, 2, ..., N と 変換したので, 逆変換. repx(i, 1, N + 1){ ic[i] = ia[tc[i]]; oc[ic[i]] = i; } // 7. (A, C), (B, C) の 距離 を チェック. // -> 順列 C を 基準に 計算. repx(i, 1, N + 1){ ca[i] = oc[ia[i]]; cb[i] = oc[ib[i]]; } LL d1 = 0, d2 = 0; BIT<LL> ft1(N + 2), ft2(N + 2); repx(i, 1, N + 1){ // 位置 ca[i], cb[i] に, 加算. ft1.add(ca[i], 1); ft2.add(cb[i], 1); // 集計. // 区間[ca[i] + 1, N + 1), [cb[i] + 1, N + 1) を 集計対象とする. d1 += ft1.sum(ca[i] + 1, N + 1); d2 += ft2.sum(cb[i] + 1, N + 1); } assert(d1 == d2); // 8. 出力. repx(i, 1, N + 1) printf("%d%s", ic[i], (i < N) ? " " : "\n"); 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 |
[入力例] 5 1 2 3 4 5 5 4 3 2 1 [出力例] 5 2 1 3 4 ※AtCoderのテストケースより ※但し, 上記のプログラムでは, 以下の内容が出力される. 1 5 4 2 3 [入力例] 5 1 2 3 4 5 1 2 4 3 5 [出力例] -1 ※AtCoderのテストケースより [入力例] 9 3 1 4 2 5 9 7 6 8 2 1 8 3 5 7 9 4 6 [出力例] 3 1 2 8 4 5 7 9 6 ※AtCoderのテストケースより [入力例] 15 2 15 13 7 8 9 4 12 6 5 10 1 3 14 11 5 9 13 14 11 10 3 8 15 4 2 1 6 7 12 [出力例] 2 15 13 7 5 9 14 11 10 8 3 4 1 6 12 [入力例] 20 11 12 8 18 20 7 4 3 9 2 13 1 19 10 17 15 16 5 14 6 5 17 1 4 14 18 2 3 19 7 9 6 15 20 10 8 12 13 16 11 [出力例] 11 12 8 18 5 17 1 4 14 2 3 19 20 7 9 6 15 10 13 16 [入力例] 50 30 36 31 3 49 16 33 21 18 13 17 38 48 32 5 6 10 2 35 24 27 46 50 41 1 4 29 39 9 37 15 44 43 42 28 19 11 47 7 8 45 22 23 14 40 25 34 20 12 26 8 23 16 43 31 37 34 48 33 41 6 18 38 27 17 4 19 1 24 30 12 25 45 13 44 36 46 11 5 40 22 9 10 26 21 47 15 42 49 20 14 32 39 2 28 29 35 7 3 50 [出力例] 30 36 31 3 49 16 33 21 18 13 17 38 48 32 5 6 10 8 23 43 37 34 41 27 4 19 1 24 12 25 45 44 46 11 40 22 9 26 47 15 42 20 14 2 39 28 29 35 7 50 [入力例] 100 48 62 26 16 19 33 76 88 31 18 82 70 96 83 10 60 66 84 58 92 52 55 78 8 54 23 11 65 59 51 7 98 85 57 63 29 13 27 22 41 24 67 72 20 69 38 45 42 71 34 74 37 97 15 73 49 99 94 3 2 4 61 5 56 79 21 50 68 87 28 77 86 46 44 32 47 14 89 100 1 43 93 40 90 80 53 81 75 17 6 12 91 35 64 39 95 30 25 9 36 68 69 71 88 84 2 49 90 77 74 20 45 47 95 24 11 62 58 72 31 41 97 43 30 6 15 91 4 96 32 55 42 100 29 8 22 80 16 59 9 26 99 36 76 18 60 75 70 38 52 57 78 54 82 21 35 94 25 44 1 3 92 89 66 37 39 87 5 86 93 33 19 27 10 79 28 40 83 81 7 14 17 46 34 65 61 51 85 23 63 53 73 56 64 98 13 48 67 50 12 [出力例] 48 62 26 16 19 33 76 88 31 18 82 70 96 83 10 60 66 84 58 92 52 55 78 8 54 23 11 65 59 51 68 69 71 2 49 90 77 74 20 45 47 95 24 72 41 97 43 30 6 15 91 4 32 42 100 29 22 80 9 99 36 75 38 57 21 35 94 25 44 1 3 89 37 39 87 5 86 93 27 79 28 40 81 7 14 17 46 34 61 85 63 53 73 56 64 98 13 67 50 12 |
■参照サイト
AtCoder Regular Contest 043