C++の練習を兼ねて, AtCoder Beginner Contest 114 の 問題C（755) ～ 問題D (756) を解いてみた.
■感想.
1. 問題C, 問題D とも, 解答に至るまでの条件が複雑だったため, 結局, ゴリゴリ書く羽目になって, 非常にきつかった.
2. 但し, 解説と, ほぼ同じ方針だったので, 及第点は, 取れたように思う.
本家のサイトABC 114 解説をご覧下さい.
■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 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
#include <bits/stdc++.h> using namespace std; #define FOR(i, a, b) for(int i = (a); i < (b); ++i) // 文字'3', '5', '7' を使って, "3" ～ "777777777" までの数を生成. // @param v: 前回生成した文字列の配列. // @param l: 再帰処理の深さ(終了条件). // @param d: 追加対象の文字列の長さ. // @param ret: 生成した文字列の配列を返却. // ex. l == 1 の場合, "33" ～ "777" の 36個の数字が生成される. vector<string> make753(vector<string> v, int l, int d) { string base = "357"; vector<string> ret = v; // Time Limit Exceeded が, テストケース b04 で発生したので, 修正. // -> N == 1 の コードテスト で, // terminate called after throwing an instance of 'std::bad_alloc' what(): std::bad_alloc // を確認したので, l== 0 -> l <= 0 に修正. if(l <= 0) return ret; else for(auto &p : v) FOR(i, 0, 3) if(p.size() == d) ret.push_back(p + base[i]); return make753(ret, --l, ++d); } int main() { // 1. 入力情報取得. string N; cin >> N; // 2. 各桁について, '3', '5', '7' と比較して, 場合の数を計算. int ans = 0; int l = N.size(); // イメージとして, "3" ～ "777777777" までの数について, // N よりも小さい七五三数を抽出出来れば, 解答となるはず. // 但し, '3', '5', '7' が, それぞれ, 1回以上出現している必要がある. // i は, 比較対象とする七五三数(もどき, 333 なども比較していくため)の桁数とする. vector<string> v = {"33", "35", "37", "53", "55", "57", "73", "75", "77"}; vector<string> cur = make753(v, l - 2, 2); // 3. 七五三数をカウントアップ. // for(auto &p : cur) cout << p << endl; for(auto &p : cur) { map<char, int> m; m['3'] = 0; m['5'] = 0; m['7'] = 0; FOR(i, 0, p.size()) m[p[i]]++; if(m['3'] > 0 && m['5'] > 0 && m['7'] > 0) { // 文字列長 が N よりも短い or 文字列の順序が, N より先の場合, カウントアップ. if(p.size() < N.size() || p <= N) { ans++; // cout << p << endl; } } } // 4. 後処理. cout << ans << endl; return 0; } |
■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 81 82 83 84 85 |
#include <bits/stdc++.h> using namespace std; #define FOR(i, a, b) for(int i = (a); i < (b); ++i) // a を b で何回割り切れるかをカウント. // @param a: 割られる数. // @param b: 割る数. // @param c: 割り切れた回数. // @return: 割り切れる回数を返却. int countDivide(int a, int b, int c){ if(a % b == 0) return countDivide(a / b, b, ++c); return c; } int main() { // 1. 入力情報取得. int N; cin >> N; // 2. 約数をカウント. int prime[25] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97}; // 各素数が何回出現するかをカウント. map<int, int> m; FOR(i, 1, N + 1) { int n = i; FOR(j, 0, 25) { if(i < prime[j]) break; int c = countDivide(i, prime[j], 0); // cout << i << " " << j << " " << c << endl; if(c != 0) m[prime[j]] += c; } } // for(auto &p : m) cout << p.first << " " << p.second << endl; // 3. 出現した素数の数に応じて, 分類. // 74回以上 現れた素数の種類数 … c74. // 24回以上74回未満現れた素数の種類数 … c14. // 14回以上24回未満現れた素数の種類数 … c14. // 4回以上14回未満現れた素数の種類数 … c4. // 2回以上 4回未満現れた素数の種類数 … c2. // を計算. int c2 = 0; int c4 = 0; int c14 = 0; int c24 = 0; int c74 = 0; for(auto &p : m) { int t = p.second; if(t >= 74) c74++; if(t >= 24 && t < 74) c24++; if(t >= 14 && t < 24) c14++; if(t >= 4 && t < 14) c4++; if(t >= 2 && t < 4) c2++; } // 4. 七五数を計算. int ans = 0; int total = c2 + c4 + c14 + c24 + c74; // 4-1. c74 だけで七五数を構築. // 75 * 1 = 75. ans += c74; // 4-2. c24, と もう一つ で七五数を構築など. // 25 * 3 = 75. ans += (total - c2 - c4 - c14) * (total - 1); // 4-3. c14, と もう一つ で七五数を構築など. // 15 * 5 = 75. ans += (total - c2 - c4) * (total - c2 - 1); // 4-4. c2, と もう二つ, もしくは, c2 以外 で七五数を構築. // 3 * 5 * 5 = 75. ans += (total - c2) * (total - c2 - 1) * c2 / 2; ans += (total - c2) * (total - c2 - 1) * (total - c2 - 2) / 2; // 5. 出力 ～ 後処理. cout << ans << endl; return 0; } |
■参照サイト
AtCoder Beginner Contest 114