C++の練習を兼ねて, AtCoder Regular Contest 033 の 問題A (A – 隠れた言葉) ~ 問題C (C – データ構造) を解いてみた.
■感想.
1. 問題C は, 遅延評価セグメント木 と 二分探索 の 組み合わせで, 解けるのでは?と気付けたので, AC版となったと思う.
2. 遅延評価セグメント木が必要なため, 下記のライブラリを拝借させて頂いた.
3. 遅延評価セグメント木 と 二分探索 を 同時に復習できたので, 非常に良かったと思う.
4. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトARC 033 解説をご覧下さい.
■C++版プログラム(問題A/AC版).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
#include <bits/stdc++.h> using namespace std; int main(){ // 1. 入力情報. int N; scanf("%d", &N); // 2. 出力. printf("%d\n", N * (N + 1) / 2); 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 |
[入力例] 1 [出力例] 1 ※AtCoderのテストケースより [入力例] 2 [出力例] 3 ※AtCoderのテストケースより [入力例] 3 [出力例] 6 ※AtCoderのテストケースより [入力例] 4 [出力例] 10 ※AtCoderのテストケースより [入力例] 1000 [出力例] 500500 |
■C++版プログラム(問題B/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 |
#include <bits/stdc++.h> using namespace std; #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 int main(){ // 1. 入力情報. int N, M, a, b; scanf("%d %d", &N, &M); set<int> A, B; rep(i, N){ scanf("%d", &a); A.insert(a); } rep(i, M){ scanf("%d", &b); B.insert(b); } // 2. 両方に現れる個数は? int AND = 0; for(auto &p : A) if(B.count(p) > 0) AND++; // 3. どちらかに現れる個数は? int OR = A.size() + B.size() - AND; // 4. Jaccard係数は? double ans = (double)AND / (double)OR; // 5. 出力. printf("%.12f\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 |
[入力例] 3 2 1 3 5 1 2 [出力例] 0.2500000000 ※AtCoderのテストケースより ※ 但し, 上記のプログラムでは, 以下の内容が出力される. 0.250000000000 [入力例] 9 10 11 2 33 4 55 6 77 8 99 10 11 14 19 55 1000000000 4 5 7 8 [出力例] 0.2666666667 ※AtCoderのテストケースより ※ 但し, 上記のプログラムでは, 以下の内容が出力される. 0.266666666667 [入力例] 50 75 17 16 1 10 26 26 21 15 16 30 3 10 21 12 3 6 15 11 15 14 14 23 16 20 8 17 13 30 12 9 2 5 8 26 17 11 1 6 15 9 6 28 26 13 21 14 3 13 25 28 18 30 12 15 24 24 19 6 17 25 27 18 18 5 17 24 1 25 8 28 18 23 2 24 27 11 15 11 14 20 12 14 6 26 15 11 23 24 12 11 6 24 13 12 21 15 5 11 29 12 7 20 8 14 14 28 22 11 10 24 2 15 7 26 13 17 23 15 15 26 18 30 8 23 13 [出力例] 0.655172413793 |
■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 |
#include <bits/stdc++.h> using namespace std; #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--) const int MAX = 202020; // ※※※ 以下のライブラリを使用(一部改変) ※※※. // 遅延評価セグメント木をソラで書きたいあなたに. // http://tsutaj.hatenablog.com/entry/2017/03/30/224339 // http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2236726 struct LazySegmentTree{ private: int n; vector<int> node, lazy; public: LazySegmentTree(vector<int> v){ int sz = (int)v.size(); n = 1; while(n < sz) n *= 2; node.resize(2 * n - 1); lazy.resize(2 * n - 1, 0); // 元配列 の 値 を, セグメント木のノード に 保存. rep(i, sz) node[i + n - 1] = v[i]; repr(i, n - 2, 0) node[i] = node[i * 2 + 1] + node[i * 2 + 2]; } void eval(int k, int l, int r){ if(lazy[k] != 0) { node[k] += lazy[k]; if(r - l > 1) { lazy[2 * k + 1] += lazy[k] / 2; lazy[2 * k + 2] += lazy[k] / 2; } lazy[k] = 0; } } void update(int a, int b, int x, int k = 0, int l = 0, int r = -1){ if(r < 0) r = n; eval(k, l, r); if(b <= l || r <= a) return; if(a <= l && r <= b){ lazy[k] += (r - l) * x; eval(k, l, r); }else{ update(a, b, x, 2 * k + 1, l, (l + r) / 2); update(a, b, x, 2 * k + 2, (l + r) / 2, r); node[k] = node[2 * k + 1] + node[2 * k + 2]; } } int query(int a, int b, int k = 0, int l = 0, int r = -1){ if(r < 0) r = n; eval(k, l, r); if(b <= l || r <= a) return 0; if(a <= l && r <= b) return node[k]; int vl = query(a, b, 2 * k + 1, l, (l + r) / 2); int vr = query(a, b, 2 * k + 2, (l + r) / 2, r); return vl + vr; } }; int main(){ // 1. 入力情報. int Q; scanf("%d", &Q); // 2. クエリに回答. LazySegmentTree seg(vector<int>(MAX, 0)); int T, X; rep(i, Q){ scanf("%d %d", &T, &X); // S に 数X を 追加. if(T == 1){ seg.update(X, MAX, 1); } // S に含まれる数で, X番目に小さい数Y を答え, その数を, S から削除. if(T == 2){ int l = 0, h = MAX, m, Y; int debug = 0; while(l < h - 1 && debug < 100){ // 中央を決める. m = (l + h) / 2; // m番目は? Y = seg.query(m, m + 1); if(Y < X) l = m; else h = m; // 無限ループ防止用. debug++; } // X番目に小さい数. printf("%d\n", h); // S から 削除. seg.update(h, MAX, -1); } } 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 |
[入力例] 5 1 11 1 29 1 89 2 2 2 2 [出力例] 29 89 ※AtCoderのテストケースより [入力例] 12 1 8932 1 183450 1 34323 1 81486 1 127874 1 114850 1 55277 1 112706 2 3 1 39456 1 52403 2 4 [出力例] 55277 52403 ※AtCoderのテストケースより [入力例] 50 1 8171 1 1995 1 11779 1 12307 1 6114 2 2 1 468 1 1963 2 5 1 2668 2 3 2 4 1 5042 1 8031 2 6 1 5725 1 8941 2 5 1 6052 1 1749 1 2179 2 1 1 8839 1 6924 2 7 1 7645 1 9064 1 753 1 10576 2 13 1 5743 1 4350 1 12240 1 4611 2 3 1 6262 1 6092 1 8246 1 3480 1 8442 2 20 1 8730 1 2417 1 694 1 4985 2 15 1 10754 1 8794 1 2448 1 7851 [出力例] 6114 11779 1995 8171 12307 5725 468 6924 10576 1963 12240 6262 |