C++の練習を兼ねて, 競プロ典型 90 問 の 問題042 (Multiple of 9) を解いてみた.
■感想.
1. 動的計画法の方針で, 規則性を抽出できたので, AC版に到達出来たと思う.
2. 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.
詳細は, 本家のサイト(GitHub) 競プロ典型 90 問 の 問題042 を ご覧下さい.
■C++版プログラム(問題042／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 |
// 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--) const LL MOD = 1e9 + 7; LL dp[101010][10]; // {各桁の和, 1の位} int main(){ // 1. 入力情報. int K; scanf("%d", &K); // 2. 例外ケース. if(K % 9 != 0){ puts("0"); return 0; } // 3. 通常ケース. rep(i, 10) dp[i][i] = 1; repx(i, 2, 100000){ // 3-1. 各桁の和(i) に対して, 1の位(j) を, すべて見る. repx(j, 1, 10){ // 3-2. 各桁の和は, 1の位以上であるはず. int b = i - j; if(b >= 0){ // 3-3. 各桁の和(b)のパターンを集計. LL dx = 0; repx(k, 1, 10){ dx += dp[b][k]; dx %= MOD; } // 3-4. dp更新. dp[i][j] += dx; dp[i][j] %= MOD; } } } // 4. 集計. LL ans = 0; repx(j, 1, 10) ans += dp[K][j], ans %= MOD; // 5. 出力. 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 |
[入力例] 1 [出力例] 0 ※AtCoderテストケースより [入力例] 234 [出力例] 757186539 ※AtCoderテストケースより [入力例] 9 [出力例] 256 [入力例] 18 [出力例] 129792 [入力例] 2025 [出力例] 789912177 |
■参照サイト
042 – Multiple of 9