C++の練習を兼ねて, AtCoder Regular Contest 101 の 問題D (Median of Medians) を解いてみた.
■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考にして, ようやく, AC版に到達出来た.
2. 実装に苦労したものの, 二分探索の復習が出来たので良かったと思う.
3. Binary Indexed Tree の 復習が出来たので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 101 解説 を ご覧下さい.
■C++版プログラム(問題D／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 |
// 解き直し. // https://img.atcoder.jp/arc101/editorial.pdf // 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--) int a[101010]; // 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, l = 2020202020, h = 0, m; scanf("%d", &N); rep(i, N){ scanf("%d", &a[i]); h = max(h, a[i]); l = min(l, a[i]); } h++; l--; // 2. 最終的な中央値となるための判定条件(要素数). LL M = (LL)(N + 1) * (LL)N / 2; if(M & 1) M++; M /= 2; // 3. 評価関数. auto f = [&](int x) -> bool { // 3-1. x以上か？ int b[N]; rep(i, N) b[i] = (a[i] >= x) ? 1 : -1; // 3-2. 数列 S の 計算. int S[N + 1]; S[0] = 0; int ms = N + 1; rep(i, N){ S[i + 1] = S[i] + b[i]; ms = min(ms, S[i + 1]); } // 3-3. Binary Indexed Tree に 数列 S を 反映. if(ms <= 0) rep(i, N + 1) S[i] += (1 - ms); BIT<LL> ft(N + 1); rep(i, N + 1) ft.add(S[i], 1LL); // 3-4. 数列 S に含まれる S[l] <= S[r] を 満たすものの個数. LL sCount = 0; rep(i, N){ // 場所 S[i] に, -1 を 加算. ft.add(S[i], -1LL); // 区間[S[i], N] の 合計は？ LL t = ft.sum(S[i], N + 1); // 集計. sCount += t; } // 3-5. 評価. return (sCount < M); }; // 4. 二分探索. while(l + 1 < h){ m = (h + l) >> 1; if(f(m)) h = m; else l = m; // printf("h=%d l=%d m=%d\n", h, l, m); } // 5. 出力. printf("%d\n", l); 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 |
[入力例] 3 10 30 20 [出力例] 30 ※AtCoderのテストケースより [入力例] 1 10 [出力例] 10 ※AtCoderのテストケースより [入力例] 10 5 9 5 9 8 9 3 5 4 3 [出力例] 8 ※AtCoderのテストケースより [入力例] 5 23 8 17 5 13 [出力例] 13 [入力例] 31 41 5 92 65 3 58 97 93 2 38 4 62 64 33 8 32 79 50 28 84 19 71 6 93 99 3 75 10 5 8 20 [出力例] 50 [入力例] 100 63238 103570 37988 54487 72815 11268 99987 23767 75684 9483 16587 64526 91308 41419 27171 53793 40890 3019 37663 103430 107127 40161 111213 64334 105258 35467 116942 47020 46193 99908 66262 43053 42826 10527 108301 109763 109706 110549 57321 10236 53967 69000 22892 94994 21748 13803 36276 96104 102159 38938 107343 18714 122886 72001 113446 51043 82827 63066 52429 20403 104493 42038 42109 123184 18246 74697 24944 18185 89514 10062 95471 3832 102967 12473 55945 92535 45840 95311 20546 104868 84779 91707 104311 27314 90949 10139 46205 109686 75876 49978 107111 90053 21028 43572 79102 119240 36299 23423 105790 106975 [出力例] 57321 |
■参照サイト
AtCoder Regular Contest 101
Binary Indexed Tree (Fenwick Tree)