C++の練習を兼ねて, AtCoder Beginner Contest 233 の 問題C (Product) ～ 問題D (Count Interval) を解いてみた.
■感想.
1. 問題Dは, 連想配列による実装を試みたが, AC版に届かなかったので, 解説を参考の上, 修正版にて, AC版に到達できた.
2. 問題Cで, 深さ優先探索の訓練を積めたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 233 解説 を ご覧下さい.
■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 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using vl = vector<LL>; using vvl = vector<vl>; #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 main(){ // 1. 入力情報. int N; LL X; scanf("%d %lld", &N, &X); vvl bags; rep(i, N){ int L; scanf("%d", &L); vl bag; rep(j, L){ LL a; scanf("%lld", &a); bag.pb(a); } bags.pb(bag); } // 2. dfs. // https://ja.wikipedia.org/wiki/深さ優先探索 auto dfs = [&](auto&& self, LL cX, int cDepth) -> int{ // 2-1. 終了条件. if(cDepth == N) return (cX == 1); // 2-2. ボールの取り出し方を数える. int ret = 0; rep(i, bags[cDepth].size()){ if(cX % bags[cDepth][i] == 0){ LL nX = cX / bags[cDepth][i]; ret += self(self, nX, cDepth + 1); } } // 2-3. 返却. return ret; }; // 3. 出力. printf("%d\n", dfs(dfs, X, 0)); 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 |
[入力例] 2 40 3 1 8 4 2 10 5 [出力例] 2 ※AtCoderテストケースより [入力例] 3 200 3 10 10 10 3 10 10 10 5 2 2 2 2 2 [出力例] 45 ※AtCoderテストケースより [入力例] 3 1000000000000000000 2 1000000000 1000000000 2 1000000000 1000000000 2 1000000000 1000000000 [出力例] 0 ※AtCoderテストケースより [入力例] 5 2020 5 2 5 10 20 40 11 1 2 4 5 10 15 20 40 50 101 202 3 1 10 202 8 1 2 2 5 8 10 10 20 12 1 1 2 2 5 5 7 10 12 20 101 202 [出力例] 73 [入力例] 7 20220112 5 1 2 4 8 16 3 1 2 4 2 1 877 3 1 8 131 5 1 2 4 8 16 3 1 1 11 7 1 2 4 11 16 131 877 [出力例] 79 |
■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 36 |
// 解き直し. // https://atcoder.jp/contests/abc233/editorial/3163 // 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--) LL a[202020], aCum[202020]; int main(){ // 1. 入力情報. int N; LL K; scanf("%d %lld", &N, &K); rep(i, N) scanf("%lld", &a[i]); // 2. 累積和. rep(i, N) aCum[i + 1] = aCum[i] + a[i]; // 3. 数え上げ(解説通り). LL ans = 0; map<LL, LL> m; repx(r, 1, N + 1){ m[aCum[r - 1]]++; ans += m[aCum[r] - K]; } // 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 |
[入力例] 6 5 8 -3 5 7 0 -4 [出力例] 3 ※AtCoderテストケースより [入力例] 2 -1000000000000000 1000000000 -1000000000 [出力例] 0 ※AtCoderテストケースより [入力例] 12 7 0 1 -9 5 10 7 -3 2 3 -6 -11 12 [出力例] 4 [入力例] 20 15 12 -21 10 14 -4 5 11 29 -6 7 -16 -10 0 14 11 -20 24 -10 1 26 [出力例] 8 [入力例] 50 123 84 3 -89 16 62 47 14 62 61 -32 24 70 29 30 -6 99 23 1 2 -18 21 90 -7 40 35 52 -4 89 -14 74 63 8 62 -84 8 109 -84 97 0 4 22 67 23 11 71 2 3 5 55 68 [出力例] 17 |
■参照サイト
AtCoder Beginner Contest 233