C++の練習を兼ねて, AtCoder Regular Contest 088 の 問題E (Papple Sort) を解いてみた.
■感想.
1. E問題は, 方針が全く見えず, 解説を確認して, AC版に到達できたので, 良かったと思う.
2. Binary Indexed Tree の 復習が出来たので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
3. 個人的には, 非常に面白い問題に感じた.
4. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Regular Contest 088 解説 を ご覧下さい.
■C++版プログラム(問題E／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 |
// 解き直し. // https://img.atcoder.jp/arc088/editorial.pdf // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; 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() int a[26], b[202020], c[202020], S[26][202020], tCount[26], T[26][202020], per[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. 入力情報. char s[202020]; scanf("%s", s); string str(s); int l = str.size(); // 2. 各文字に対して, 出現回数を割り当てる. rep(i, l){ // 2-1. 各文字の出現回数. int idx = str[i] - 'a'; a[idx]++; // 2-2. 各文字(位置)に対する出現回数. b[i] = a[idx]; // 2-3. 各文字, 出現回数 に 紐づく 出現位置 を 保存. S[idx][a[idx]] = i + 1; } // 3. 奇数回しか出てこない文字を調査. int odd = 0; rep(i, 26) if(a[i] & 1) odd++; if(odd >= 2){ puts("-1"); return 0; } // 4. 回文作成後 の 左, 中央, 右 の 位置判定. rep(i, l){ int idx = str[i] - 'a'; // 4-1. 奇数(最大1つ). if(a[idx] & 1){ if(b[i] * 2 == a[idx] + 1) c[i] = 2; // 中央. else if(b[i] * 2 < a[idx] + 1) c[i] = 1; // 左. else if(b[i] * 2 > a[idx] + 1) c[i] = 3; // 右. } // 4-2. 偶数. if(!(a[idx] & 1)){ if(b[i] * 2 <= a[idx]) c[i] = 1; // 左. else c[i] = 3; // 右. } } // 5. 文字列 X 作成. vector<P> X; rep(i, l) X.pb({c[i], i}); sort(all(X)); // rep(i, l) printf("o=%d p=%d\n", X[i].a, X[i].b); // 6. 変換: X -> T. // 左, 中央のみ対応する. rep(i, (l + 1) / 2){ // 6-1. 文字列 X から 一文字取得. P p = X[i]; // 6-2. 出現回数を保存. int x = str[p.b] - 'a'; int y = ++tCount[x]; // 6-3. 文字列 T における 位置情報 を保存. if(y * 2 <= a[x] + 1){ T[x][y] = i + 1; T[x][a[x] + 1 - y] = l - i; } } // rep(i, 26){ // repx(j, 1, a[i] + 1) printf("i=%d j=%d s=%d t=%d\n", i, j, S[i][j], T[i][j]); // } // 7. 順列 per を 作成. // -> S[i][j] -> T[i][j] への変換を保存. rep(i, 26) repx(j, 1, a[i] + 1) per[S[i][j]] = T[i][j]; // 8. バブルソートの交換回数を集計. BIT<LL> ft(l + 1); LL ans = 0; repx(i, 1, l + 1){ // 8-1. per[i] に, 1 を 加算. ft.add(per[i], 1LL); // 8-2. 区間[0, per[i]] の 合計は？ LL t = ft.sum(0, per[i] + 1); // 8-3. 転倒数を集計. ans += (LL)per[i] - t; } // 9. 出力. 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 |
[入力例] eel [出力例] 1 ※AtCoderテストケースより [入力例] ataatmma [出力例] 4 ※AtCoderテストケースより [入力例] snuke [出力例] -1 ※AtCoderテストケースより [入力例] abcabcabcabcabcabc [出力例] 9 [入力例] abracadabra [出力例] -1 [入力例] edaceabdaeabcaedabaeadbaecabdaeabaedcabeadabeadcabadabd [出力例] 88 |
■参照サイト
AtCoder Regular Contest 088
Binary Indexed Tree (Fenwick Tree)