C++の練習を兼ねて, AtCoder Regular Contest 136 の 問題A (A ↔ BB) ～ 問題B (Triple Shift) を解いてみた.
■感想.
1. 問題Bは, 実装してみたもののWA版となったため, 解説を参考に, 解き直ししてAC版に到達できた.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 136 解説 の 各リンク を ご覧下さい.
■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 58 59 60 61 62 |
// 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 pb push_back #define all(x) x.begin(), x.end() int main(){ // 1. 入力情報. int N; char s[202020]; scanf("%d %s", &N, s); // 2. 文字列操作. stack<char> st; rep(i, N){ // 空でない. if(!st.empty()){ // 'B' の 場合. char cur = st.top(); if(cur == 'B'){ // BA -> BBB -> AB if(s[i] == 'A'){ st.pop(); st.push('A'); st.push('B'); continue; } // BB -> A if(s[i] == 'B'){ st.pop(); st.push('A'); continue; } } } // それ以外. st.push(s[i]); } // 3. 文字列作成. string ans; while(!st.empty()){ char t = st.top(); st.pop(); ans.pb(t); } // 4. 反転. reverse(all(ans)); // 5. 出力. printf("%s\n", ans.c_str()); 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 |
[入力例] 4 CBAA [出力例] CAAB ※AtCoderのテストケースより [入力例] 1 A [出力例] A ※AtCoderのテストケースより [入力例] 6 BBBCBB [出力例] ABCA ※AtCoderのテストケースより [入力例] 50 BAACACBABBACABCBBCBCBBCABAABCABACCCBABBBCCABCCABBB [出力例] AABCACAAABCABCACBCACAAAACAABCCCAAACCABCCAAB [入力例] 100 BBAABAABBCABAAABCBBCAABAAABAACBBCABCCBCCCCAACCCBBABBCBBACBCACABAABBBABAAABBBCBABABBBBCCBAACBCBBACCBA [出力例] AAAAAABCAAAAACACAAAAAAAACACABCCBCCCCAACCCAAACAACBCACAAAAAAAAAAACAAAAACCAABCBCAACCAB |
■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 |
// 説き直し. // https://atcoder.jp/contests/arc136/editorial/3467 // 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[5050], b[5050], ca[5050], cb[5050]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); set<int> st; rep(i, N){ scanf("%d", &a[i]); ca[a[i]]++; st.insert(a[i]); } rep(i, N){ scanf("%d", &b[i]); cb[b[i]]++; } // 2. 例外. rep(i, 5050){ if(ca[i] != cb[i]){ puts("No"); return 0; } } // 3. sort. // 3-1. 数列 A. int aCnt = 0; rep(i, N){ int aMin = 5050, at = -1; repx(j, i, N){ if(aMin > a[j]){ aMin = a[j]; at = j; } } repr(j, at, i + 1) swap(a[j], a[j - 1]); aCnt += (at - i); } // 3-2. 数列 B. int bCnt = 0; rep(i, N){ int bMin = 5050, at = -1; repx(j, i, N){ if(bMin > b[j]){ bMin = b[j]; at = j; } } repr(j, at, i + 1) swap(b[j], b[j - 1]); bCnt += (at - i); } // 4. 出力. if(st.size() != N) puts("Yes"); else printf("%s\n", ((aCnt + bCnt) % 2 == 0) ? "Yes" : "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 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 |
[入力例] 4 3 1 4 5 4 1 5 3 [出力例] Yes ※AtCoderのテストケースより [入力例] 3 1 2 2 2 1 2 [出力例] Yes ※AtCoderのテストケースより [入力例] 3 1 2 3 2 3 4 [出力例] No ※AtCoderのテストケースより [入力例] 7 2 1 3 5 4 7 6 1 5 6 7 2 4 3 [出力例] No [入力例] 20 10 1 7 8 10 6 3 8 5 4 6 1 2 11 9 12 3 7 10 1 7 3 10 1 8 1 2 4 3 1 6 5 6 7 12 11 9 10 8 10 [出力例] Yes [入力例] 50 15 25 8 34 36 50 49 44 42 11 7 21 17 27 31 30 19 43 46 5 12 16 45 33 23 13 22 35 9 1 10 41 48 20 38 28 26 6 32 18 29 2 24 39 4 3 40 37 14 47 34 7 46 27 4 43 24 40 31 13 38 45 29 23 11 30 9 39 25 10 50 19 44 36 5 3 47 8 17 37 42 15 16 22 49 1 41 32 14 20 33 26 28 18 2 12 48 35 6 21 [出力例] Yes |
■参照サイト
AtCoder Regular Contest 136