C++の練習を兼ねて, AtCoder Grand Contest 022 の 問題A (Diverse Word) ～ 問題B (GCD Sequence) を解いてみた.
■感想.
1. 問題A, Bは, 解答方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 個人的には, 問題A, B ともに, 非常に面白い問題に感じた.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Grand Contest 022 解説 を ご覧下さい.
■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 63 64 65 66 |
// 解き直し. // https://img.atcoder.jp/agc022/editorial.pdf // 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 int memo[26]; int main(){ // 1. 入力情報. char c[33]; scanf("%s", c); string S(c); int N = S.size(); string ans = ""; // 2. 多彩な単語を構成. // 2-1. 26文字未満. if(N < 26){ // 出現した文字情報を保存. ans = S; rep(i, N) memo[S[i] - 'a']++; // 出現していない文字を探索. rep(i, 26){ if(!memo[i]){ ans.pb((char)('a' + i)); break; } } } // 2-2. 26文字. if(N == 26){ // 接尾辞(index)を抽出. int idx = 0; repr(i, N - 2, 0){ if(S[i] < S[i + 1]){ idx = i + 1; break; } } // idx = 0 の 場合. if(!idx) ans = "-1"; // idx != 0 の 場合. if(idx){ char q = 'z'; repx(i, idx, N) if(S[idx - 1] < S[i]) q = min(q, S[i]); ans = S.substr(0, idx); ans.pop_back(); ans.pb(q); } } // 3. 出力. 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 38 39 40 41 42 43 44 45 |
[入力例] atcoder [出力例] atcoderb ※AtCoderテストケースより [入力例] abc [出力例] abcd ※AtCoderテストケースより [入力例] zyxwvutsrqponmlkjihgfedcba [出力例] -1 ※AtCoderテストケースより [入力例] abcdefghijklmnopqrstuvwzyx [出力例] abcdefghijklmnopqrstuvx ※AtCoderテストケースより [入力例] btcjhnlfyiadxmrezovqkusgpw [出力例] btcjhnlfyiadxmrezovqkusgw [入力例] mwrpxhaeznjsdkcvfiyqutolgb [出力例] mwrpxhaeznjsdkcvfiyt [入力例] odzvwbhirtxqgmpyusnlkjfeca [出力例] odzvwbhirtxqgms |
■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 |
// 解き直し. // https://img.atcoder.jp/agc022/editorial.pdf // 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 pb push_back const int EVEN[] = {2, 10, 3, 9, 4, 8, 6, 12}; const int ODD[] = {6, 2, 10, 3, 9, 4, 8, 12}; int main(){ // 1. 入力情報. int N; scanf("%d", &N); // 2. Sを構成. // 2-1. N = 3. vi ans; if(N == 3) ans.pb(2), ans.pb(5), ans.pb(63); // 2-2. それ以外. bool odd = (N & 1); if(N > 3){ // 奇数. if(odd) rep(i, N) ans.pb(12 * (i / 8) + ODD[i % 8]); // 偶数. if(!odd) rep(i, N) ans.pb(12 * (i / 8) + EVEN[i % 8]); } // 3. 出力. 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 |
[入力例] 3 [出力例] 2 5 63 ※AtCoderテストケースより [入力例] 4 [出力例] 2 5 20 63 ※AtCoderテストケースより ※但し, 上記のプログラムでは, 以下の内容が出力される. 2 10 3 9 [入力例] 25 [出力例] 6 2 10 3 9 4 8 12 18 14 22 15 21 16 20 24 30 26 34 27 33 28 32 36 42 [入力例] 111 [出力例] 6 2 10 3 9 4 8 12 18 14 22 15 21 16 20 24 30 26 34 27 33 28 32 36 42 38 46 39 45 40 44 48 54 50 58 51 57 52 56 60 66 62 70 63 69 64 68 72 78 74 82 75 81 76 80 84 90 86 94 87 93 88 92 96 102 98 106 99 105 100 104 108 114 110 118 111 117 112 116 120 126 122 130 123 129 124 128 132 138 134 142 135 141 136 140 144 150 146 154 147 153 148 152 156 162 158 166 159 165 160 164 |
■参照サイト
AtCoder Grand Contest 022