C++の練習を兼ねて, AtCoder Beginner Contest 170 の 問題D (Not Divisible) を解いてみた.
■感想.
1. 実装方針が決まるまで苦労したものの, 何とかAC版となった.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトABC 170 解説をご覧下さい.
■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 |
// 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 pb push_back int a[1010101], cnt[1010101], d[1010101]; int main(){ // 1. 入力情報. int N; set<int> s; scanf("%d", &N); rep(i, N){ scanf("%d", &a[i]); cnt[a[i]]++; s.insert(a[i]); } // 2. 割り切れるか確認. for(auto &p : s){ repex(i, p * 2, 1010101, p) if(cnt[i]) d[i]++; } // 3. 出力. int ans = 0; rep(i, N) if(cnt[a[i]] == 1 && !d[a[i]]) ans++; 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 |
[入力例] 5 24 11 8 3 16 [出力例] 3 ※AtCoderテストケースより [入力例] 4 5 5 5 5 [出力例] 0 ※AtCoderテストケースより [入力例] 10 33 18 45 28 8 19 89 86 2 4 [出力例] 5 ※AtCoderテストケースより [入力例] 30 87 12 64 100 57 48 54 18 91 63 81 94 13 17 5 99 98 77 85 56 64 72 33 16 84 60 44 50 92 2 [出力例] 10 [入力例] 50 186 33 122 31 138 129 149 32 22 144 163 27 153 180 140 199 111 42 128 177 36 88 131 29 61 131 91 171 89 38 26 48 122 29 149 186 151 184 124 19 144 123 65 174 113 183 186 106 49 186 [出力例] 28 |
■参照サイト
AtCoder Beginner Contest 170