C++の練習を兼ねて, AtCoder Beginner Contest 152 の 問題D (Handstand 2) ~ 問題E (Flatten) を解いてみた.
■感想.
1. 問題D, Eは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 両問ともに, 解説のロジックで, 計算できることが, 非常に印象深く残ったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 152 解説 を ご覧下さい.
■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 |
// 解き直し. // https://img.atcoder.jp/abc152/editorial.pdf #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--) LL c[10][10]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); // 2. c[i][j] を 計算(解説通り). rep(n, N){ string sn = to_string(n + 1); int i = sn.front() - '0'; int j = sn.back() - '0'; ++c[i][j]; } // 3. 集計. // -> 解説の数式を適用. LL ans = 0; rep(i, 10) rep(j, 10) ans += c[i][j] * c[j][i]; // 4. 出力. printf("%lld\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 57 58 59 60 61 62 63 64 65 66 |
[入力例] 25 [出力例] 17 ※AtCoderテストケースより [入力例] 1 [出力例] 1 ※AtCoderテストケースより [入力例] 100 [出力例] 108 ※AtCoderテストケースより [入力例] 2020 [出力例] 40812 ※AtCoderテストケースより [入力例] 200000 [出力例] 400000008 ※AtCoderテストケースより [入力例] 333 [出力例] 1152 [入力例] 8849 [出力例] 783233 [入力例] 21230 [出力例] 4507137 [入力例] 20200119 [出力例] 4080448480152 ※整数 N が, 問題文の制約条件から範囲外であるケース. [入力例] 123456789 [出力例] 152415789971049 ※整数 N が, 問題文の制約条件から範囲外であるケース. |
■C++版プログラム(問題E/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 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 |
// 解き直し. // https://img.atcoder.jp/abc152/editorial.pdf #include <bits/stdc++.h> using namespace std; using LL = long long; using MP = map<int, 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 a first #define b second const LL MOD = 1e9 + 7; int b[1010101]; LL a[10101]; // 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: 素因数分解 の 結果 を 返却. MP div(int X){ // X を 2で割り切れなくなるまで割っていく. map<int, int> ret; while(!(X % 2)) ++ret[2], X >>= 1; // X を 3以上の奇数で, 割り切れなくなるまで順次割っていく. repex(i, 3, sqrt(X) + 1, 2){ while(!(X % i)){ ++ret[i]; X /= i; } } // X が 2 より 大きな素数であれば, 追加. if(X > 2) ++ret[X]; // 出力. return ret; } // Fermat's little theorem から, 大きな冪乗の計算を行う. // @param a: べき乗したい正整数. // @param b: 指数. // @return: べき乗した計算結果(mod版). LL mPow(LL a, LL b){ LL t = 1; while(b){ if(b & 1) t = (t * a) % MOD; a = a * a % MOD; b >>= 1; } return t; } int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N) scanf("%lld", &a[i]); // 2. 素数を取得. repx(i, 2, 1010101){ if(b[i]) continue; repex(j, i * 2, 1010101, i) b[j]++; } // 3. 素数を集計. MP lcm; repx(i, 2, 1010101) if(!b[i]) lcm[i] = 0; // 4. 素因数分解を行う. rep(i, N){ MP m = div(a[i]); for(auto &p : m) lcm[p.a] = max(lcm[p.a], p.b); } // 5. L を 計算(解説通り). LL L = 1; for(auto &p : lcm){ rep(i, p.b){ L *= (LL)p.a; L %= MOD; } } // 6. 集計. // -> 解説の数式を適用. LL ans = 0; rep(i, N){ ans += L * mPow((LL)a[i], MOD - 2); ans %= MOD; } // 7. 出力. printf("%lld\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 57 58 |
[入力例] 3 2 3 4 [出力例] 13 ※AtCoderテストケースより [入力例] 5 12 12 12 12 12 [出力例] 5 ※AtCoderテストケースより [入力例] 3 1000000 999999 999998 [出力例] 996989508 ※AtCoderテストケースより [入力例] 3 1 2 3 [出力例] 11 [入力例] 5 2 6 12 24 108 [出力例] 173 [入力例] 7 3 1 4 1 5 9 2 [出力例] 611 [入力例] 10 1 2 3 4 5 6 7 8 9 10 [出力例] 7381 [入力例] 11 78 108 34 111 19 73 52 85 9 36 64 [出力例] 606380251 |
■参照サイト
AtCoder Beginner Contest 152