C++の練習を兼ねて, AtCoder Beginner Contest 245 の 問題C (Choose Elements) ~ 問題D (Polynomial division) を解いてみた.
■感想.
1. 問題C, Dは, 方針を絞り込めたので, AC版に到達出来た.
2. 問題Cで, 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 245 解説 の 各リンク を ご覧下さい.
■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 |
// 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[202020], b[202020]; bool dp[202020][2]; int main(){ // 1. 入力情報. int N, K; scanf("%d %d", &N, &K); rep(i, N) scanf("%d", &a[i]); rep(i, N) scanf("%d", &b[i]); // 2. dp更新. dp[0][0] = dp[0][1] = true; repx(i, 1, N){ // 2-1. 前回, a[i - 1] が, 条件を満たしていた. if(dp[i - 1][0]){ if(abs(a[i] - a[i - 1]) <= K) dp[i][0] = true; if(abs(b[i] - a[i - 1]) <= K) dp[i][1] = true; } // 2-2. 前回, b[i - 1] が, 条件を満たしていた. if(dp[i - 1][1]){ if(abs(a[i] - b[i - 1]) <= K) dp[i][0] = true; if(abs(b[i] - b[i - 1]) <= K) dp[i][1] = true; } } // 3. 出力. printf("%s\n", (dp[N - 1][0] || dp[N - 1][1]) ? "Yes" : "No"); 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 |
[入力例] 5 4 9 8 3 7 2 1 6 2 9 5 [出力例] Yes ※AtCoderテストケースより [入力例] 4 90 1 1 1 100 1 2 3 100 [出力例] No ※AtCoderテストケースより [入力例] 4 1000000000 1 1 1000000000 1000000000 1 1000000000 1 1000000000 [出力例] Yes ※AtCoderテストケースより [入力例] 5 10 15 12 16 1 12 4 23 8 21 10 [出力例] Yes [入力例] 10 20 18 15 67 84 82 99 41 22 59 65 52 36 33 13 30 33 72 63 85 34 [出力例] No [入力例] 30 50 5 22 76 137 183 197 135 149 129 160 88 128 155 91 98 17 119 150 122 144 93 172 195 123 99 72 123 100 182 166 50 77 122 185 99 172 222 185 99 123 111 100 77 123 189 69 22 49 65 35 172 176 135 150 140 109 135 150 150 131 [出力例] Yes |
■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 |
// 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[303], b[303], c[606]; int main(){ // 1. 入力情報. int N, M; scanf("%d %d", &N, &M); rep(i, N + 1) scanf("%d", &a[i]); rep(i, N + M + 1) scanf("%d", &c[i]); // 2. b を 計算. rep(i, M + 1){ // 計算済みの係数を除外. int d = c[N + M - i]; rep(j, i) if(N + j >= i && M >= j) d -= a[N - i + j] * b[M - j]; // 今回分更新. b[M - i] = d / a[N]; } // 3. 出力. rep(i, M + 1) printf("%d%s", b[i], (i < M) ? " " : "\n"); 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 |
[入力例] 1 2 2 1 12 14 8 2 [出力例] 6 4 2 ※AtCoderテストケースより [入力例] 1 1 100 1 10000 0 -1 [出力例] 100 -1 ※AtCoderテストケースより [入力例] 3 5 5 1 3 7 15 8 30 33 45 81 31 62 63 [出力例] 3 1 4 1 5 9 [入力例] 7 3 3 1 4 1 5 9 2 6 6 2 14 10 20 28 16 40 22 16 12 [出力例] 2 0 2 2 [入力例] 10 7 1 7 3 2 0 5 0 8 0 7 5 2 14 8 20 20 23 27 55 64 52 53 24 78 26 69 29 52 30 [出力例] 2 0 2 2 0 3 2 6 |
■参照サイト
AtCoder Beginner Contest 245