C++の練習を兼ねて, AtCoder Grand Contest 034 の 問題A (Kenken Race) ～ 問題B (ABC) を解いてみた.
■感想.
1. 問題A, B ともに, 方針が見えなかったので, 解説を見て提出したところ, AC版に到達できたので, 良かったと思う.
2. Binary Indexed Tree の 復習が出来たので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Grand Contest 034 解説 を ご覧下さい.
■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 54 55 56 57 |
// C++(GCC 9.2.1) // 解き直し. // https://img.atcoder.jp/agc034/editorial.pdf #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 main(){ // 1. 入力情報. int N, A, B, C, D; char S[202020]; scanf("%d %d %d %d %d %s", &N, &A, &B, &C, &D, S); A--, B--, C--, D--; // 2. 2マス連続で, 岩があるか？ bool rock2 = false; repx(i, A, max(C - 1, D - 1)){ if(S[i] == '#' && S[i + 1] == '#'){ rock2 = true; break; } } // 3. 判定. // 3-1. C < D の 場合. if(C < D && !rock2){ puts("Yes"); return 0; } // 3-2. C > D の 場合. if(C > D){ // 3マス連続で, 空きスペースがあるか？ bool free3 = false; // repx(i, B, min(N - 1, D)){ // handmade_09 の WA回避. repx(i, B, min(N - 1, D + 1)){ if(S[i - 1] == '.' && S[i] == '.' && S[i + 1] == '.'){ free3 = true; break; } } // 2マス連続で, 岩がない, かつ, 3マス連続で, 空きスペースがある. if(!rock2 && free3){ puts("Yes"); return 0; } } // 3-3. それ以外. puts("No"); 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 |
[入力例] 7 1 3 6 7 .#..#.. [出力例] Yes ※AtCoderのテストケースより [入力例] 7 1 3 7 6 .#..#.. [出力例] No ※AtCoderのテストケースより [入力例] 15 1 3 15 13 ...#.#...#.#... [出力例] Yes ※AtCoderのテストケースより |
■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 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 |
// C++(GCC 9.2.1) // 解き直し. // https://img.atcoder.jp/agc034/editorial.pdf #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--) #define pof pop_front #define pob pop_back #define pub push_back #define puf push_front // Binary Indexed Tree (Fenwick Tree) // https://youtu.be/lyHk98daDJo?t=7960 template<typename T> struct BIT{ int n; vector<T> d; BIT(int n = 0) : n(n), d(n + 1) {} void add(int i, T x = 1){ for(i++; i <= n; i += i & -i) d[i] += x; } T sum(int i){ T x = 0; for(i++; i; i -= i & -i) x += d[i]; return x; } T sum(int l, int r){ return sum(r - 1) - sum(l - 1); } }; int main(){ // 1. 入力情報. char s[202020]; scanf("%s", s); string S(s); // 2. "BC" -> 'D' に 置き換え. deque<char> dq; for(auto &x : S){ // 2-1. deque が 空でない場合. if(!dq.empty()){ // 2-2. deque の 末尾を取得. char c = dq.back(); // 2-3. "BC" が 見つかった場合は, deque の 'B' を 捨てて, 'D' を 積む. if(c == 'B' && x == 'C'){ dq.pob(); dq.pub('D'); continue; } // 2-4. "BC" が 見つからなかった場合は, deque に そのまま積む. dq.pub(x); continue; } // 2-5. deque が, 空の場合. dq.pub(x); } // 3. 文字列を分割. vector<string> v; string t = ""; while(!dq.empty()){ // 3-1. deque の 先頭を取得 char c = dq.front(); dq.pof(); // 3-2. 'A' or 'D' の 場合. if(c == 'A' || c == 'D'){ t.pub(c); continue; } // 3-3. 'B' or 'C' の 場合. if(t.size()) v.pub(t), t = ""; } // 3-4. 一番最後を考慮. if(t.size()) v.pub(t); // 4. 集計. LL ans = 0; for(auto &x : v){ // 4-1. BIT を 設定. int l = x.size(); BIT<LL> ft(l + 1); // 4-2. 'A' の 個数 を 集計. rep(i, l){ // 'A' が 出現した場合. if(x[i] == 'A') ft.add(i, 1LL); // 'D' が 出現した場合, すでに出現した 'A' の 個数 を 加算. if(x[i] == 'D') ans += ft.sum(0, i + 1); } } // 5. 出力. 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 |
[入力例] ABCABC [出力例] 3 ※AtCoderのテストケースより [入力例] C [出力例] 0 ※AtCoderのテストケースより [入力例] ABCACCBABCBCAABCB [出力例] 6 ※AtCoderのテストケースより [入力例] ABCCBCBBAAABBBACABCCBCCCABCCBBAABABBBABABBABCCABBCBBBCCBBCBBACACCCAACCABCABCCCBCABBBABABBCACBBBBBCCB [出力例] 7 [入力例] CABBACBABABABBABACABCCCABBCCBCAABAAABCCBCBCBABBCABBBBCACAACAAACAACCBCCABBCAABAAABCBBBCCBAACBABBABBBCCCBAAABBACCCCCCBCCACCCAAABCABBCACACCBBBBBBCBCBCCCBAAACCCBBBBCBBBAACACACBBACBBCBCBCABACBABACCCACCCACCBBCACAABACCBACACBABACCACACABCAAABABCBAAABBBBCCABCBCACBACBABACBBBABCCACBCABCBBAAACAAAACCCBAABACAAACBABABCCCCBAAAACAAABACACCCCBACBBCCBBBBCBCBABCBBBBBCBBCBCCCBCAABCBAACBABBCACABACCBBBABAACBBBCBBABBBBAABACACAAAACCCCCBABCCBBBCBCACBABBCAAAABABBACACACCBAAABCBAACAABACCACCBBBCACCBCBABACBBABBBBAABCCAAACBBAACA [出力例] 26 [入力例] AACBBCCACCBCAABBABAABABBCCBBBBACCCBBBBBBCCBCCAABCACBCACBCAAACABCABCBCCBBAAABCCBBABABCBCABCBACACABCCAABCAAACBAACBCABCBCBCCCBBBBAABBCACCCBAAAACABCBBBBCABACCCBBCCACACCACBABACBAABABCCABBABBBABCABBCCBCBACCBAABABAAACACBBAACACCBAACBABAABCAAACCAAABBCCBCACBACCBCBCCABCBBCBCAAACBACCBBAABBCCCBABBCCACCBAABBBBBAABACBACBBBBBACBAACCCBAACCBABBABBACAABBBCCCBCBCBBCBAACBCCCACCBCBBABCBACAACACAACACABAABCCABCCCBBACCBBCBBBCCCBCBACBACBBBABCCACBCCAACBBACCACABABAABABACBCAAAAACCCCACBACCBABBCBBBABACABBCBBAAAAAAACBAAAABAABBABACAAABBCABBCBACBACACBBCCCABACBBCBBABBBBBCCCACCBCACBBACBACABCACABBCAAABCAABBBACACCCCCACBAABCCCAAACAAACCCBABCABBBBABBAAAABABBBBBBCBBAAABBBBBACABCBCCAAAACAACBAAAABCCABCCABCCABABAACACBABABCCBBCAABCCBABBABCCABBCACABBACCBBCCBABBABBABBBAAACBABBACCAAACBCABCBCABBBCCCCCAABCCCCBBBCABACACCACABACACCBBBACCCABCABAABCBBBABABACACCABACCBCBBCBBBABACABBBCABBCCAAABCCBABBBAACAACBBBBBCCBACACBCCBCACBBBBCBBABBBBCBAABAAACBBCACCABBBACABABCCACACCBACCCBCCCCABCBABBAABBACACACCBCAAACABAABCABCBACACACCBAABBCCBBBABBCAABCAAABBCCA [出力例] 69 |
■参照サイト
AtCoder Grand Contest 034
Binary Indexed Tree (Fenwick Tree)