C++の練習を兼ねて, AtCoder Regular Contest 044 の 問題A (素数判定) ～ 問題B (最短路問題) を解いてみた.
■感想.
1. 問題B は, 数え上げ部分で, 方針が見えなかったので, 解説を参考に, ようやくAC版となった.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトAtCoder Regular Contest 044 解説をご覧下さい.
■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 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 |
// 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 // 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; scanf("%d", &N); // 2. 素因数分解. map<int, int> m = div(N); // 3. 素数判定. // 3-1. 1 の 場合. if(N == 1){ puts("Not Prime"); return 0; } // 3-2. 素数の場合. bool ok = false; // ex. // 125 は, Not Prime の はず. // -> test_03.txt, test_06.txt, test_07.txt の WA版 になった理由. // if(m.size() == 1) ok = true; if(m.size() == 1){ int c = m.begin()->b; if(c == 1){ puts("Prime"); return 0; } } // 3-3. 合成数の場合. string n = to_string(N); int d = n.size(); int f = 2; // 1 の 位 が 偶数でも, 5 でない. int d1 = n[d - 1] - '0'; if(d1 % 2 != 0 && d1 != 5) f--; // 各桁の和. int d2 = 0; rep(i, d) d2 += n[i] - '0', d2 %= 3; if(d2 % 3 != 0) f--; // 判定. if(f == 0) ok = true; // 4. 出力. printf("%s\n", ok ? "Prime" : "Not Prime"); 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 |
[入力例] 42 [出力例] Not Prime ※AtCoderのテストケースより [入力例] 49 [出力例] Prime ※AtCoderのテストケースより [入力例] 3 [出力例] Prime ※AtCoderのテストケースより [入力例] 1 [出力例] Not Prime ※AtCoderのテストケースより [入力例] 125 [出力例] Not Prime [入力例] 12345678 [出力例] Not Prime [入力例] 1234567 [出力例] Prime [入力例] 123456789 [出力例] Not Prime |
■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 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 |
// 解き直し. // https://www.slideshare.net/chokudai/arc044 // 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--) const LL MOD = 1e9 + 7; const int LIMIT = 101010; int a[LIMIT], d[LIMIT]; // 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 % MOD; } int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N){ scanf("%d", &a[i]); d[a[i]]++; } // 2. グラフの個数は？ // 2-1. 頂点 1 の 距離が, 0 より 大きい場合, または, 距離 0 が 複数個ある場合. if(a[0] || d[0] > 1){ puts("0"); return 0; } // 3-2. それ以外の場合. LL ans = 1; int count = 1, bef = 1; repx(i, 1, 101010){ // 距離 i の 頂点数. int cur = d[i]; // 頂点数 が N 未満で, 距離 i の 頂点がない. if(count < N && cur == 0){ puts("0"); break; } // グラフの個数をカウント. // 距離 i - 1 と 距離 i の 頂点同士 の 結び付き方. LL t = mPow(2LL, (LL)bef); t += MOD - 1; t %= MOD; ans *= mPow(t, (LL)cur); ans %= MOD; // 距離 i の 頂点同士 の 結び付き方. ans *= mPow(2LL, (LL)(cur - 1) * (LL)cur / 2LL); ans %= MOD; // 確認した頂点数 を 保存. count += cur; // 前回分更新. bef = cur; // 頂点数 が N に 到達したら, 終了. if(count == N){ printf("%lld\n", ans); break; } } 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 |
[入力例] 4 0 1 1 2 [出力例] 6 ※AtCoderのテストケースより [入力例] 4 0 1 2 0 [出力例] 0 ※AtCoderのテストケースより [入力例] 3 1 1 2 [出力例] 0 ※AtCoderのテストケースより [入力例] 17 0 1 1 2 2 4 3 2 4 5 3 3 2 1 5 4 2 [出力例] 855391686 ※AtCoderのテストケースより [入力例] 23 0 1 6 5 2 3 7 2 2 3 3 4 4 5 6 7 7 8 9 10 8 9 11 [出力例] 930127887 |
■参照サイト
AtCoder Regular Contest 044