C++の練習を兼ねて, AtCoder Regular Contest 123 の 問題A (Deforestation) ~ 問題B (Increasing Triples) を解いてみた.
■感想.
1. 問題A, B は, 規則性を抽出できたので, AC版に到達出来たと思う.
2. 問題B で, 標準ライブラリ std::deque を使う練習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 123 解説 の 各リンク を ご覧下さい.
■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 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; int main(){ // 1. 入力情報. LL A, B, C; scanf("%lld %lld %lld", &A, &B, &C); // 2. 入れ替え. if(A > C) swap(A, C); // 3. 等差数列になるように調整. // ex. // 1 1000000000000000 2 // -> 1999999999999997 が 正解のはず. LL ans = 202020202020202020, D = A + C; if(D & 1){ if(C - B > B - A) ans = min(ans, (D + 1) / 2 - B + 1); // else ans = min(ans, B + B - D - 1); // 02_rand_03.txt などの WA対応. else ans = min(ans, B + B - D); }else{ if(C - B > B - A) ans = min(ans, D / 2 - B); else ans = min(ans, B + B - D); } // 4. 出力. printf("%lld\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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
[入力例] 4 8 10 [出力例] 2 ※AtCoderのテストケースより [入力例] 10 3 4 [出力例] 4 ※AtCoderのテストケースより [入力例] 1 2 3 [出力例] 0 ※AtCoderのテストケースより [入力例] 1000000000000000 1 1000000000000000 [出力例] 999999999999999 ※AtCoderのテストケースより [入力例] 1 1000000000000000 2 [出力例] 1999999999999997 [入力例] 31415 92653 58979 [出力例] 94912 [入力例] 14 14 21 [出力例] 5 [入力例] 173 20 50 [出力例] 93 |
■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 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 |
// C++(GCC 9.2.1) #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 pof pop_front #define pob pop_back #define pub push_back #define puf push_front int a[101010], b[101010], c[101010]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N) scanf("%d", &a[i]); rep(i, N) scanf("%d", &b[i]); rep(i, N) scanf("%d", &c[i]); // 2. sort. sort(a, a + N); sort(b, b + N); sort(c, c + N); // 3. dequeに保存. deque<int> dqA, dqB, dqC; rep(i, N) dqA.pub(a[i]); rep(i, N) dqB.pub(b[i]); rep(i, N) dqC.pub(c[i]); // 4. a[i] < b[i] < c[i] を カウント. int ans = 0; while(!dqA.empty()){ // 4-1. 初期化. int sa = 0, sb = 0, sc = 0; // 4-2. 整数列 A から取得. sa = dqA.front(); dqA.pof(); // 4-3. 整数列 B から 取得. while(!dqB.empty()){ sb = dqB.front(); dqB.pof(); if(sb > sa) break; } // 4-4. 整数列 C から取得. while(!dqC.empty()){ sc = dqC.front(); dqC.pof(); if(sc > sb) break; } // 4-5. チェック. if(sa < sb && sb < sc) ans++; // 4-6. 継続するか? if(dqB.empty() || dqC.empty()) break; } // 5. 出力. 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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
[入力例] 5 9 6 14 1 8 2 10 3 12 11 15 13 5 7 4 [出力例] 3 ※AtCoderのテストケースより [入力例] 1 10 20 30 [出力例] 1 ※AtCoderのテストケースより [入力例] 3 1 1 1 1 1 2 2 2 2 [出力例] 0 ※AtCoderのテストケースより [入力例] 10 85 106 100 9 110 34 57 114 11 110 86 16 39 5 64 43 122 106 29 67 38 68 98 110 88 37 111 5 60 112 [出力例] 6 [入力例] 20 82 71 54 91 7 98 26 35 35 13 50 1 70 108 37 69 94 95 12 68 22 89 68 76 3 16 11 100 86 73 123 101 59 123 97 1 39 59 61 109 51 28 48 45 26 119 98 68 20 84 11 74 59 95 65 74 69 117 47 49 [出力例] 15 [入力例] 100 9 14 21 39 50 35 20 42 27 50 17 20 8 9 19 48 46 38 38 47 39 19 14 19 5 34 5 27 39 6 35 47 30 2 30 2 31 43 16 36 18 40 20 22 7 13 5 22 20 16 8 44 38 16 10 2 8 27 49 5 42 4 40 25 31 41 38 5 25 35 29 9 31 48 16 29 29 25 22 36 11 45 30 34 38 28 2 47 13 1 49 3 34 7 22 15 16 18 49 26 38 31 48 7 32 46 15 46 40 6 24 19 39 39 38 46 3 29 45 11 25 20 35 36 30 3 19 41 44 17 26 43 36 10 16 19 22 10 13 9 30 50 20 41 6 41 10 43 41 20 6 18 1 18 4 17 45 16 36 48 50 50 24 36 22 18 11 9 14 34 18 2 38 20 1 17 13 8 10 4 31 47 36 32 16 7 40 22 49 38 32 15 35 8 12 46 37 6 35 27 23 20 31 5 28 2 19 22 22 41 44 19 34 38 3 8 9 13 7 21 17 33 27 26 3 11 21 39 34 31 8 12 41 12 4 3 23 37 43 30 5 43 9 37 43 50 5 42 33 8 19 12 29 12 46 39 5 35 23 49 45 10 39 3 40 32 9 3 31 33 6 44 31 10 9 28 39 17 18 19 24 22 23 16 13 2 7 2 17 26 47 15 30 37 9 26 23 23 23 28 [出力例] 78 |
■参照サイト
AtCoder Regular Contest 123