C++の練習を兼ねて, AtCoder Beginner Contest 148 の 問題D (D – Brick Break) を解いてみた.
■感想.
1. 解説見る前に, AC版となったので良かったと思う.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイトABC 148解説をご覧下さい.
■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 |
#include <bits/stdc++.h> using namespace std; 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 a first #define b second #define pb push_back const int MAX = 202020; int a[MAX]; vector<P> block; int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N){ scanf("%d", a + i); block.pb({a[i], i}); } // 2. sort. sort(block.begin(), block.end()); // for(auto& p : block) printf("%d %d\n", p.a, p.b); // 3. レンガ を 1 2 ... K のように残すには? int res = 0, cur = 1, index = -1; for(auto& p : block){ if(cur == p.a && p.b > index){ // 残すレンガの数をインクリメント. res++; // 次のレンガを探すため, index更新. index = p.b; // 次のレンガを探すため, インクリメント. cur++; } } // 4. 出力. int ans = N - res; printf("%d\n", (ans == N) ? -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 |
[入力例] 3 2 1 2 [出力例] 1 ※AtCoderテストケースより [入力例] 3 2 2 2 [出力例] -1 ※AtCoderテストケースより [入力例] 10 3 1 4 1 5 9 2 6 5 3 [出力例] 7 ※AtCoderテストケースより [入力例] 1 1 [出力例] 0 ※AtCoderテストケースより [入力例] 20 1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 7 5 6 7 8 [出力例] 12 [入力例] 250 93 14 45 33 97 76 1 7 96 2 55 31 97 91 74 3 76 17 15 18 38 4 94 52 85 62 69 5 39 89 6 39 80 78 79 39 9 76 7 97 50 95 62 29 70 21 17 99 6 46 7 43 14 8 4 89 16 72 58 60 14 14 9 94 11 82 9 31 9 69 56 10 11 95 93 24 51 37 65 12 66 81 75 52 87 36 19 11 61 19 10 13 80 29 17 13 83 14 75 95 42 26 36 15 95 87 34 31 16 84 74 99 60 72 19 17 94 20 95 47 66 85 92 8 4 31 39 44 18 84 95 34 34 17 96 17 27 61 18 31 34 14 39 5 92 26 51 19 22 81 88 20 89 48 41 54 20 89 31 20 65 3 14 23 76 33 28 63 4 83 31 14 72 29 83 21 29 16 22 15 23 33 20 61 93 27 79 23 4 51 19 23 79 68 24 8 84 24 60 11 24 75 15 55 33 94 66 16 54 14 44 67 81 86 78 11 83 62 85 95 9 84 25 10 89 23 82 76 58 22 71 88 99 85 40 72 74 99 52 70 82 48 72 22 39 67 59 80 14 23 [出力例] 225 |
■参照サイト
AtCoder Beginner Contest 148