C++の練習を兼ねて, AtCoder Beginner Contest 215 の 問題C (One More aab aba baa) ~ 問題D (Coprime 2) を解いてみた.
■感想.
1. 問題Dは, TLE版を回避できなかったので, 解説を参考に, AC版に到達できたと思う.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 215 解説 の 各リンク を ご覧下さい.
■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 47 48 |
// 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 #define all(x) x.begin(), x.end() int main(){ // 1. 入力情報. char c[11]; int K; scanf("%s %d", c, &K); string s(c); // 2. 分離後の二数の積を全探索. int n = s.size(); vi z(n); iota(all(z), 0); set<string> st; do{ // 並び替え. string cur; rep(i, n) cur.pb(s[z[i]]); // 保存. st.insert(cur); }while(next_permutation(all(z))); // 3. K 番目は? int d = 0; string ans; for(auto &x : st){ if(++d == K){ ans = x; break; } } // 4. 出力. 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 |
[入力例] aab 2 [出力例] aba ※AtCoderテストケースより [入力例] baba 4 [出力例] baab ※AtCoderテストケースより [入力例] ydxwacbz 40320 [出力例] zyxwdcba ※AtCoderテストケースより [入力例] atcoder 2022 [出力例] drtaoec [入力例] graph 99 [出力例] rahgp [入力例] algorithm 202020 [出力例] magolitrh ※文字列 S が, 問題文の制約条件から範囲外であるケース. |
■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 |
// 解き直し. // https://atcoder.jp/contests/abc215/editorial/2482 // 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 a first #define b second int a[101010], memo[101010]; // Efficient program to print all prime factors of a given number // https://www.geeksforgeeks.org/print-all-prime-factors-of-a-given-number/ // 与えられた正整数についての素因数分解を計算. // @param X: 素因数分解を行う整数. // @return ret: 素因数分解 の 結果 を 返却. map<int, int> div(int X){ // 1. X を 2で割り切れなくなるまで割っていく. map<int, int> ret; while(!(X % 2)) ret[2]++, X >>= 1; // 2. X を 3以上の奇数で, 割り切れなくなるまで順次割っていく. repex(i, 3, sqrt(X) + 1, 2){ while(!(X % i)){ ret[i]++; X /= i; } } // 3. X が 2 より 大きな素数であれば, 追加. if(X > 2) ret[X]++; // 4. 出力. return ret; } int main(){ // 1. 入力情報. int N, M; scanf("%d %d", &N, &M); rep(i, N) scanf("%d", &a[i]); // 2. 初期化. set<int> ans; rep(i, M) ans.insert(i + 1); // 3. 素因数分解. rep(i, N){ map<int, int> m = div(a[i]); for(auto &x : m){ int p = x.a; if(!memo[p]){ ++memo[p]; repex(j, p, M + 1, p) ans.erase(j); } } } // 4. 出力. printf("%d\n", ans.size()); for(auto &x : ans) printf("%d\n", x); 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 |
[入力例] 3 12 6 1 5 [出力例] 3 1 7 11 ※AtCoderテストケースより [入力例] 5 17 3 1 4 1 5 [出力例] 5 1 7 11 13 17 [入力例] 20 100 13 23 35 77 121 61 31 29 49 83 19 37 43 125 25 17 41 19 11 23 [出力例] 30 1 2 3 4 6 8 9 12 16 18 24 27 32 36 47 48 53 54 59 64 67 71 72 73 79 81 89 94 96 97 |
■参照サイト
AtCoder Beginner Contest 215