C++の練習を兼ねて, AtCoder Beginner Contest 133 の 問題D (D – Rain Flows into Dams) を解いてみた.
■感想.
1. 相変わらず苦手な DP の訓練となったと思う.
2. 解答を見る前に, 解けたので, 及第点は取れたと思う.
本家のサイトABC 133解説をご覧下さい.
■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 37 38 39 40 41 42 43 44 45 46 47 48 49 |
#include <bits/stdc++.h> using namespace std; using LL = long long; const int MAX = 1e5; LL A[MAX]; LL dp[MAX]; int main() { // 1. 入力情報取得. int N; scanf("%d", &N); for(int i = 0; i < N; i++) scanf("%d", A + i); // 2. 各山に降った雨の量を計算. // ex. // 以下のように, 各山に, 雨が降った(リットル: L)とする. // 山1 = 2 * x1 [L] // 山2 = 2 * x2 [L] // 山3 = 2 * x3 [L] // 山4 = 2 * x4 [L] // 山5 = 2 * x5 [L] // // この場合, 各ダムは, 以下のように水が溜まるので, // ダム1 = x1 + x2 [L] // ダム2 = x2 + x3 [L] // ダム3 = x3 + x4 [L] // ダム4 = x4 + x5 [L] // ダム5 = x5 + x1 [L] // => ダム1 - ダム2 + ダム3 - ダム4 + ダム5 で, 山1 の 降雨量 2 * x1 [L] が 抽出できる. // 2-1. 山1 の 降雨量 を 取得. LL r = 0; for(int i = 0; i < N; i++){ if(i % 2 == 0) r += A[i]; else r -= A[i]; } // 2-2. 山2 ～ 山N の 降雨量 を 取得. // ex. // 山2 は, ダム1: x1 + x2 から 山1 の 降雨量 2 * x1 [L] の 半分 を 引けば, // x2 が残るので, 2 * x2 とすれば, 山2 の 降雨量 が 計算出来たことになる. dp[0] = r; for(int i = 1; i < N; i++) dp[i] = 2 * (A[i - 1] - dp[i - 1] / 2); // 3. 後処理. for(int i = 0; i < N; i++) printf("%lld ", dp[i]); 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 |
[入力例] 3 2 2 4 [出力例] 4 0 4 ※AtCoderテストケースより [入力例] 5 3 8 7 5 5 [出力例] 2 4 12 2 8 ※AtCoderテストケースより [入力例] 3 1000000000 1000000000 0 [出力例] 0 2000000000 0 ※AtCoderテストケースより [入力例] 7 1 1 2 2 3 7 4 [出力例] 0 2 0 4 0 6 8 [入力例] 101 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99 99 97 95 93 91 89 87 85 83 81 79 77 75 73 71 69 67 65 63 61 59 57 55 53 51 49 47 45 43 41 39 37 35 33 31 29 27 25 23 21 19 17 15 13 11 9 7 5 3 1 0 [出力例] 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 84 86 88 90 92 94 96 98 100 98 96 94 92 90 88 86 84 82 80 78 76 74 72 70 68 66 64 62 60 58 56 54 52 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2 0 |
■参照サイト
AtCoder Beginner Contest 133