C++の練習を兼ねて, AtCoder Grand Contest 026 の 問題A (Colorful Slimes 2) ～ 問題B (rng_10s) を解いてみた.
■感想.
1. 問題A は, stack の 復習ができたので, 良かったと思う.
2. 問題B は, 解答方針が見えなかったので, 解説を参考に実装したところ, AC版に到達できたので良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Grand Contest 026 解説 を ご覧下さい.
■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 |
// 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--) int a[111]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N) scanf("%d", &a[i]); // 2. 魔法を唱える最小回数は？ stack<int> st; rep(i, N){ if(st.size() > 0 && st.top() == a[i]) st.pop(), st.push(0); // 魔法を唱えたら, 意図的に, 0 を 保存. else st.push(a[i]); } // 3. 出力. printf("%d\n", N - st.size()); 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 |
[入力例] 5 1 1 2 2 2 [出力例] 2 ※AtCoderのテストケースより [入力例] 3 1 2 1 [出力例] 0 ※AtCoderのテストケースより [入力例] 5 1 1 1 1 1 [出力例] 2 ※AtCoderのテストケースより [入力例] 14 1 2 2 3 3 3 4 4 4 4 1 2 3 4 [出力例] 4 ※AtCoderのテストケースより [入力例] 33 3 3 4 4 1 5 1 5 5 1 6 6 2 2 2 2 7 1 6 1 6 6 4 6 2 6 7 2 3 4 2 6 3 [出力例] 7 |
■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 |
// 解き直し. // https://img.atcoder.jp/agc026/editorial.pdf // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; #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--) int main(){ // 1. 入力情報. int T; scanf("%d", &T); // 2. クエリ回答. rep(i, T){ // 2-1. 入力情報. LL A, B, C, D; scanf("%lld %lld %lld %lld", &A, &B, &C, &D); // 2-2. 初日でジュース買えない場合. if(B > A){ puts("No"); continue; } // 2-3. 初日でジュース買えた場合. if(B <= A){ // 仮に毎日入荷したとしても購入量に追いつけない場合. if(B > D){ puts("No"); continue; } // 仮に毎日入荷し, 購入量以上である場合. if(B <= D){ // 買う量が閾値以下であり, 買切る前に必ず入荷が発生した場合. if(C >= B){ puts("Yes"); continue; } // それ以外. if(C < B){ LL g = __gcd(B, D); LL o = A; o %= g; o += (B - g); printf("%s\n", (o > C) ? "No" : "Yes"); } } } } 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 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 |
[入力例] 14 9 7 5 9 9 7 6 9 14 10 7 12 14 10 8 12 14 10 9 12 14 10 7 11 14 10 8 11 14 10 9 11 9 10 5 10 10 10 5 10 11 10 5 10 16 10 5 10 1000000000000000000 17 14 999999999999999985 1000000000000000000 17 15 999999999999999985 [出力例] No Yes No Yes Yes No No Yes No Yes Yes No No Yes ※AtCoderのテストケースより [入力例] 24 1 2 3 4 1 2 4 3 1 3 2 4 1 3 4 2 1 4 2 3 1 4 3 2 2 1 3 4 2 1 4 3 2 3 1 4 2 3 4 1 2 4 1 3 2 4 3 1 3 1 2 4 3 1 4 2 3 2 1 4 3 2 4 1 3 4 1 2 3 4 2 1 4 1 2 3 4 1 3 2 4 2 1 3 4 2 3 1 4 3 1 2 4 3 2 1 [出力例] No No No No No No Yes Yes No No No No Yes Yes Yes No No No Yes Yes Yes No No No ※AtCoderのテストケースより [入力例] 22 360 679 774 997 896 96 409 173 66 87 31 27 623 54 40 618 35 961 15 25 72 42 708 972 45 410 520 92 563 780 489 941 441 440 837 878 227 496 950 817 6150 77 378 350 425 3267 724 4470 73 863 58 6360 121 53 3452 708 8667 781 731 9187 916 581 12 766 4532 2639 8565 8053 57 613 504 1753 378 500 3423 3924 140 64 44 208 643 253 909 725 259 2627 2288 7629 [出力例] No Yes No No No Yes No No Yes No Yes No No Yes No No Yes No No No Yes No |
■参照サイト
AtCoder Grand Contest 026