C++の練習を兼ねて, 競プロ典型 90 問 の 問題025 (Digit Product Equation) を解いてみた.
■感想.
1. 問題025は, 方針が見えなかったので, (問題025 (Digit Product Equation) 解説) を参考に実装したところ, AC版に到達出来た.
2. 個人的には, 深さ優先探索の訓練を積めたので, 非常に良かったと思う.
3. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.
詳細は, 本家のサイト(GitHub) 競プロ典型 90 問 の 問題025 を ご覧下さい.
■C++版プログラム(問題025／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 |
// 解き直し. // https://github.com/E869120/kyopro_educational_90/blob/main/editorial/025.jpg // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; #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 #define pb push_back #define all(x) x.begin(), x.end() int main(){ // 1. 入力情報. LL N, B; scanf("%lld %lld", &N, &B); // 2. N の 桁数. string ns = to_string(N); int n = ns.size(); // 3. B に '0' が 含まれるか？ int ans = 0; bool b = false; string nb = to_string(B); rep(i, nb.size()) if(nb[i] == '0') b = true; if(b && (N >= B)) ans++; // 4. dfs. // https://ja.wikipedia.org/wiki/深さ優先探索 map<string, int> memo; auto dfs = [&](auto&& self, string fBef, int d) -> void { // 2-1. 終了条件. if(d == 0) return; // 2-2. '1' ～ '9' を 追加. // 今回分反映. repx(i, 1, 10){ // 整数を生成. string fCur = fBef; fCur.pb('0' + i); // sort. sort(all(fCur)); // 探索済か？ if(!memo.count(fCur)){ // 訪問済みを設定. memo[fCur]++; // 条件を満たす整数があるか？ // -> m を 生成して, 文字列化したものが, fCur と 等しいか？ LL fm = 1; rep(j, fCur.size()) fm *= (LL)(fCur[j] - '0'); LL m = fm + B; string sm = to_string(m); sort(all(sm)); // in12.txt などで, WA版となったので, ロジック修正(※m <= N 追加). if(m <= N && fCur == sm) ans++; // 次へ. self(self, fCur, d - 1); } } }; dfs(dfs, "", n); // 5. 出力. printf("%d\n", ans); 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 |
[入力例] 999 434 [出力例] 2 ※AtCoderテストケースより [入力例] 255 15 [出力例] 2 ※AtCoderテストケースより [入力例] 9999999999 1 [出力例] 0 ※AtCoderテストケースより [入力例] 1 1 [出力例] 0 [入力例] 123 234 [出力例] 0 [入力例] 2022 208 [出力例] 4 [入力例] 25252525 31415 [出力例] 3 [入力例] 333333333 5050 [出力例] 2 [入力例] 32100123 252525 [出力例] 2 |
■参照サイト
025 – Digit Product Equation
問題025 (Digit Product Equation) 解説