C++の練習を兼ねて, AtCoder Regular Contest 138 の 問題A (Larger Score) を解いてみた.
■感想.
1. 問題Aは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 解説にあるロジックで, 操作回数の最小値が計算できることが, 非常に印象深く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 138 解説 を ご覧下さい.
■C++版プログラム(問題A／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 |
// 解き直し. // https://atcoder.jp/contests/arc138/editorial/3746 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using P = pair<int, int>; using PQ = priority_queue<int>; using vi = vector<int>; using vp = vector<P>; #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 all(x) x.begin(), x.end() int main(){ // 1. 入力情報. int N, K; scanf("%d %d", &N, &K); vi a(N); vp op(N); rep(i, N){ scanf("%d", &a[i]); op[i].a = a[i]; op[i].b = -i; } // 2. sort. sort(all(op)); // 3. 操作回数の最小値は？ int ans = 2020202020; PQ pq; for(auto &p : op){ int i = -p.b; if(i < K){ pq.push(i); continue; } if(!pq.empty()){ int j = pq.top(); if(i >= K && a[j] < a[i]) ans = min(ans, i - j); } } // 4. 出力. printf("%d\n", (ans == 2020202020) ? -1 : 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 39 40 41 42 43 44 45 46 47 48 49 50 51 |
[入力例] 4 2 2 1 1 2 [出力例] 2 ※AtCoderのテストケースより [入力例] 3 1 3 2 1 [出力例] -1 ※AtCoderのテストケースより [入力例] 20 13 90699850 344821203 373822335 437633059 534203117 523743511 568996900 694866636 683864672 836230375 751240939 942020833 865334948 142779837 22252499 197049878 303376519 366683358 545670804 580980054 [出力例] 13 ※AtCoderのテストケースより [入力例] 7 3 3 2 5 1 6 3 7 [出力例] 2 [入力例] 10 3 3 1 4 1 5 9 2 6 5 3 [出力例] 2 [入力例] 20 5 33 77 55 88 121 30 33 22 34 78 56 123 89 125 11 222 99 5 100 50 [出力例] 7 [入力例] 100 7 1111 3333 1112 3333 2222 3333 2223 100 282 208 1111 138 257 173 88 1111 345 234 118 1110 252 65 91 234 30 234 108 260 21 126 57 97 95 1110 200 234 234 72 1111 77 1111 66 99 222 1110 170 282 281 345 1111 292 226 174 209 1110 122 1110 219 179 345 167 345 1110 169 193 345 1111 170 234 1 1110 211 100 345 1110 211 1110 100 211 133 123 1110 222 108 78 1111 197 345 100 100 1000 1112 1113 2223 3334 2224 1110 1111 100 101 [出力例] 88 |
■参照サイト
大和証券プログラミングコンテスト2022 Spring(AtCoder Regular Contest 138)