C++の練習を兼ねて, AtCoder Regular Contest 034 の 問題A (A – 首席) ～ 問題C (C – 約数かつ倍数) を解いてみた.
■感想.
1. 問題C は, 方針が見えなかったので, 解説を確認して実装したところ, ようやくAC版となった.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトARC 034 解説をご覧下さい.
■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 |
#include <bits/stdc++.h> using namespace std; int main(){ // 1. 入力情報. int N; scanf("%d", &N); // 2. 最終得点が高い受験生の最終得点は？ int maxScore = 0; while(N){ // 得点を集計. int a, b, c, d, e, score; scanf("%d %d %d %d %d", &a, &b, &c, &d, &e); score = 900 * (a + b + c + d) + 110 * e; // 最大値を更新. maxScore = max(maxScore, score); // decrement. N--; } // 3. 出力. double ans = (double)maxScore / 900.0; printf("%.12f\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 |
[入力例] 2 37 54 68 66 802 58 108 106 103 871 [出力例] 481.4555555555555555 ※AtCoderのテストケースより ※ 但し, 上記のプログラムでは, 以下の内容が出力される. 481.455555555556 [入力例] 2 80 120 120 120 900 0 0 0 0 731 [出力例] 550 ※AtCoderのテストケースより ※ 但し, 上記のプログラムでは, 以下の内容が出力される. 550.000000000000 |
■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 |
#include <bits/stdc++.h> using namespace std; using LL = long long; #define pb push_back int main(){ // 1. 入力情報. LL N; scanf("%lld", &N); // 2. 条件を満たす正整数 x を 求める. vector<LL> v; LL x = max(N - 162LL, 1LL); while(x <= N){ // f(x) を 計算. LL f = 0, a = x; while(a) f += (a % 10), a /= 10; // x + f(x) = N か？ if(x + f == N) v.pb(x); // increment. x++; } // 3. 出力. printf("%d\n", v.size()); for(auto &p : v) printf("%lld\n", p); 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 |
[入力例] 8 [出力例] 1 4 ※AtCoderのテストケースより [入力例] 101 [出力例] 2 91 100 ※AtCoderのテストケースより [入力例] 108 [出力例] 0 ※AtCoderのテストケースより [入力例] 2019 [出力例] 2 1995 2013 [入力例] 2020 [出力例] 1 2009 [入力例] 2021 [出力例] 2 1996 2014 [入力例] 1000000007 [出力例] 2 999999940 1000000003 [入力例] 10000000000007 [出力例] 3 9999999999895 9999999999904 10000000000003 |
■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 |
// C++(GCC 9.2.1) // 解き直し. // https://www.slideshare.net/chokudai/arc034 #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 const LL MOD = 1e9 + 7; map<LL, LL> divisors; // 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: 特に無し. void div(LL X){ // 1. X を 2で割り切れなくなるまで割っていく. while(X % 2 == 0) divisors[2]++, X >>= 1; // 2. X を 3以上の奇数で, 割り切れなくなるまで順次割っていく. int c = 3; while(c <= sqrt(X)){ while(X % c == 0){ divisors[c]++; X /= c; } c += 2; } // 3. X が 2 より 大きな素数であれば, 追加. if(X > 2) divisors[X]++; // 4. 終了. return; } int main(){ // 1. 入力情報. LL A, B; scanf("%lld %lld", &A, &B); // 2. 解説通り. // -> A! / B! を 考え, (B + 1) ～ A までの正整数について, 素因数分解する. int N = (int)(A - B); repx(i, 1, N + 1) div(B + (LL)i); // 3. 数え上げる. LL ans = 1; for(auto &p : divisors) ans *= (p.b + 1), ans %= MOD; // 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 |
[入力例] 3 2 [出力例] 2 ※AtCoderのテストケースより [入力例] 15 4 [出力例] 2592 ※AtCoderのテストケースより [入力例] 1000000 999900 [出力例] 21398499 ※AtCoderのテストケースより [入力例] 1000000000 999999900 [出力例] 745508745 ※AtCoderのテストケースより [入力例] 314159265 314159200 [出力例] 291734010 |
■参照サイト
AtCoder Regular Contest 034