C++の練習を兼ねて, AtCoder Beginner Contest 237 の 問題C (kasaka) ～ 問題D (LR insertion) を解いてみた.
■感想.
1. 問題C, Dは, 方針を絞ることができたので, AC版に到達できたと思う.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 237 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題C／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 |
// 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 main(){ // 1. 入力情報. char s[1010101]; scanf("%s", s); string S(s); int n = S.size(); // 2. 左側, 右側の連続する a の 個数. int l = 0, r = 0; rep(i, n){ if(S[i] == 'a') l++; else break; } repr(i, n - 1, 0){ if(S[i] == 'a') r++; else break; } // 3. 先頭に, "a" を 追加. string a(max(0, r - l), 'a'); S = a + S; // 4. 回文判定. bool ok = true; n = S.size(); rep(i, n / 2){ if(S[i] != S[n - 1 - i]){ ok = false; break; } } // 5. 出力. printf("%s\n", ok ? "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 |
[入力例] kasaka [出力例] Yes ※AtCoderテストケースより [入力例] atcoder [出力例] No ※AtCoderテストケースより [入力例] php [出力例] Yes ※AtCoderテストケースより [入力例] atblhqkpcahhacpkqhlbtaaaa [出力例] Yes [入力例] adfyrropcrwceybofnluxjsjxulnfobyecwrcporryfdaaaa [出力例] Yes |
■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 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 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using vi = vector<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 repr(i, a, b) for(int i = a; i >= b; i--) #define pob pop_back #define pof pop_front #define pub push_back #define puf push_front int main(){ // 1. 入力情報. int N; char s[505050]; scanf("%d %s", &N, s); // 2. 操作. deque<int> dqL, dqR; dqL.pub(0); rep(i, N){ // 'L' の 時. if(s[i] == 'L'){ // 左側に, i が ある. if(dqL.back() == i){ dqR.puf(i); dqL.pob(); dqL.pub(i + 1); continue; } // 右側に, i が ある. if(dqR.front() == i) dqL.pub(i + 1); } // 'R' の 時. if(s[i] == 'R'){ // 右側が, 空の場合. // -> 001.txt などで, WA版となったため, 修正. if(dqR.empty()){ dqR.puf(i + 1); continue; } // 右側に, i が ある. if(dqR.front() == i){ dqL.pub(i); dqR.pof(); dqR.puf(i + 1); continue; } // 左側に, i が ある. if(dqL.back() == i) dqR.puf(i + 1); } } // 3. 数列 A. vi ans; while(!dqL.empty()){ ans.pub(dqL.front()); dqL.pof(); } while(!dqR.empty()){ ans.pub(dqR.front()); dqR.pof(); } // 4. 出力. int n = ans.size(); rep(i, n){ printf("%d", ans[i]); printf("%s", (i < n - 1) ? " " : "\n"); } 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 |
[入力例] 5 LRRLR [出力例] 1 2 4 5 3 0 ※AtCoderテストケースより [入力例] 7 LLLLLLL [出力例] 7 6 5 4 3 2 1 0 ※AtCoderテストケースより [入力例] 10 LLRLRRRLRL [出力例] 2 4 5 6 8 10 9 7 3 1 0 [入力例] 30 LLRRLLRLRRLRRRLLRRLRRRRLLLRRLL [出力例] 2 3 6 8 9 11 12 13 16 17 19 20 21 22 26 27 30 29 28 25 24 23 18 15 14 10 7 5 4 1 0 [入力例] 50 RRLRLLLRRLRRLLLLRRLRLLRLRLLLLRLRLLLLRRLRRRLRRLRLRL [出力例] 0 1 3 7 8 10 11 16 17 19 22 24 29 31 36 37 39 40 41 43 44 46 48 50 49 47 45 42 38 35 34 33 32 30 28 27 26 25 23 21 20 18 15 14 13 12 9 6 5 4 2 |
■参照サイト
AtCoder Beginner Contest 237