C++の練習を兼ねて, 競プロ典型 90 問 の 問題030 (K Factors) を解いてみた.
■感想.
1. 実装方針を決めることができたので, AC版に到達出来たと思う.
2. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.
詳細は, 本家のサイト(GitHub) 競プロ典型 90 問 の 問題030 を ご覧下さい.
■C++版プログラム(問題030／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 |
// 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--) int a[30303030]; int main(){ // 1. 入力情報. int N, K; scanf("%d %d", &N, &K); // 2. 倍数を保存. repx(i, 2, N + 1){ if(a[i]) continue; repex(j, i, N + 1, i) a[j]++; } // 3. K種類以上をカウント. int ans = 0; rep(i, N + 1) if(a[i] >= K) ans++; // 4. 出力. 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 |
[入力例] 15 2 [出力例] 5 ※AtCoderテストケースより [入力例] 30 2 [出力例] 13 ※AtCoderテストケースより [入力例] 200 4 [出力例] 0 ※AtCoderテストケースより [入力例] 869120 1 [出力例] 869119 ※AtCoderテストケースより [入力例] 10000000 3 [出力例] 6798027 ※AtCoderテストケースより [入力例] 2021 4 [出力例] 83 [入力例] 20210707 3 [出力例] 13978430 ※整数 N が, 問題文の制約条件から範囲外であるケース. [入力例] 20210711 8 [出力例] 11 ※整数 N が, 問題文の制約条件から範囲外であるケース. |
■参照サイト
030 – K Factors