C++の練習を兼ねて, Educational DP Contest / DP まとめコンテスト の 問題M (M – Candies) を解いてみた.
■感想.
1. 解答に時間かかったものの正答出来たので, アップロードしてみた.
2. 飴 を N人にK個配る場合と, (N – 1)人に, K個以下配る場合の関係を抽出出来たので, 解答に到達することが出来たと思う.
3. 引き算を行う場合のMOD計算で躓いたので, 今後の実装で, 注意しようと思う.
■C++版プログラム(問題M／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 |
#include <bits/stdc++.h> using namespace std; using LL = long long; const LL MOD = 1e9 + 7; // N人 に K個 の 飴 を配る場合の総数を保管. LL dp[101][100001]; // 各子供(1, 2, ..., N) が受け取る飴の個数上限. LL A[101]; int main() { // 1. 入力情報取得. LL N, K; cin >> N >> K; for(LL i = 1; i <= N; i++) cin >> A[i]; // 2. 飴 の 配り方を確認. // dp[N][K] = // dp[N - 1][K - 0] (N人目 に 0個配る場合) + // dp[N - 1][K - 1] (N人目 に 1個配る場合) + // dp[N - 1][K - 2] (N人目 に 2個配る場合) + // ... // dp[N - 1][K - A[N]] (N人目 に A[N]個配る場合) // のような関係が成り立つことに注意. // ※但し, 第二成分 K - XX が, 0以上となる必要がある. // 2-1. 1人目の情報. for(LL j = 0; j <= A[1]; j++) dp[1][j] = 1; // 2-2. 2人目以降の情報. for(LL i = 2; i <= N; i++){ dp[i][0] = dp[i - 1][0]; for(LL j = 1; j <= K; j++){ dp[i][j] = dp[i][j - 1]; dp[i][j] += dp[i - 1][j], dp[i][j] %= MOD; // 1_04, 1_05, 1_07, 1_10 で, WA となったので, MOD計算 を修正. // if(j > A[i]) dp[i][j] -= dp[i - 1][j - 1 - A[i]], dp[i][j] %= MOD; if(j > A[i]) dp[i][j] += MOD, dp[i][j] -= dp[i - 1][j - 1 - A[i]], dp[i][j] %= MOD; } } // for(LL i = 0; i <= N; i++){ // for(LL j = 0; j <= K; j++) cout << dp[i][j] << " "; // cout << endl; // } // 3. 出力. cout << dp[N][K] << endl; 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 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 |
[入力例] 3 4 1 2 3 [出力例(debug版)] 0 0 0 0 0 1 1 0 0 0 1 2 2 1 0 1 3 5 6 5 5 ※AtCoderのテストケースより [入力例] 1 10 9 [出力例(debug版)] 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 ※AtCoderのテストケースより [入力例] 2 0 0 0 [出力例(debug版)] 0 1 1 1 ※AtCoderのテストケースより [入力例] 4 100000 100000 100000 100000 100000 [出力例] 665683269 ※AtCoderのテストケースより [入力例] 2 7 3 4 [出力例(debug版)] 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 1 2 3 4 4 3 2 1 1 [入力例] 2 6 3 4 [出力例(debug版)] 0 0 0 0 0 0 0 1 1 1 1 0 0 0 1 2 3 4 4 3 2 2 [入力例] 5 7 1 2 3 4 5 [出力例(debug版)] 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 2 2 1 0 0 0 0 1 3 5 6 5 3 1 0 1 4 9 15 20 22 20 15 1 5 14 29 49 71 90 101 101 [入力例] 5 7 2 3 4 5 6 [出力例(debug版)] 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 1 2 3 3 2 1 0 0 1 3 6 9 11 11 9 6 1 4 10 19 30 41 49 52 1 5 15 34 64 105 154 205 205 |