C++の練習を兼ねて, AtCoder Regular Contest 098 の 問題E (Range Minimum Queries) を解いてみた.
■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に実装して, AC版に到達できたので, 良かったと思う.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Regular Contest 098 解説 を ご覧下さい.
■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 |
// 解き直し. // https://img.atcoder.jp/arc098/editorial.pdf // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using PQ = priority_queue<int, vector<int>, greater<int>>; using vpq = vector<PQ>; #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 a[2020]; int main(){ // 1. 入力情報. int N, K, Q; scanf("%d %d %d", &N, &K, &Q); rep(i, N) scanf("%d", &a[i]); // 2. 最小値 X を 固定して 最大値 Y を チェック. int ans = 2020202020; rep(i, N){ // 2-1. 最小値 X を 設定. int X = a[i]; // 2-2. 数列の分割. vpq vPQ; PQ pq; rep(j, N + 1){ // i, j が 等しい場合も含めるようにする. if(X <= a[j]){ pq.push(a[j]); }else{ if(pq.size()) vPQ.pb(pq), pq = {}; } } // 2-3. 分割後の各数列について, 数列のサイズを, m とした場合に, // 小さい方から, 最大(m - K + 1)個まで抽出. pq = {}; rep(j, vPQ.size()){ int idx = vPQ[j].size() - K + 1; while(!vPQ[j].empty() && idx > 0){ // 数列の要素を取得. int y = vPQ[j].top(); vPQ[j].pop(); // 最大値 Y の 候補 を 追加. pq.push(y); // デクリメント. idx--; } } // 2-4. Q番目 に 小さいものを取得. int Y = -1, qIdx = Q; while(!pq.empty() && qIdx > 0){ // Y を 更新. Y = pq.top(); pq.pop(); // デクリメント. qIdx--; }; // 2-5. Y - X の 最小値 を 更新. if(!qIdx && Y != -1) ans = min(ans, Y - X); } // 3. 出力. printf("%d\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 |
[入力例] 5 3 2 4 3 1 5 2 [出力例] 1 ※AtCoderテストケースより [入力例] 10 1 6 1 1 2 3 5 8 13 21 34 55 [出力例] 7 ※AtCoderテストケースより [入力例] 11 7 5 24979445 861648772 623690081 433933447 476190629 262703497 211047202 971407775 628894325 731963982 822804784 [出力例] 451211184 ※AtCoderテストケースより [入力例] 30 7 12 13 8 7 3 14 11 13 5 7 15 1 6 12 15 14 11 2 3 13 6 4 7 15 3 11 10 7 12 14 10 [出力例] 5 [入力例] 100 11 22 10 57 60 48 16 11 102 62 71 23 20 80 23 29 25 40 49 103 90 61 123 39 104 41 58 122 41 59 115 75 83 25 121 101 87 4 87 72 110 8 31 78 42 120 56 46 88 55 85 69 37 41 63 76 52 106 118 27 8 114 33 73 6 8 27 95 63 52 88 98 28 8 103 95 38 52 36 123 72 37 53 47 25 89 12 22 53 39 80 35 44 56 107 72 109 39 43 102 91 76 [出力例] 23 |
■参照サイト
AtCoder Regular Contest 098