C++の練習を兼ねて, AtCoder Beginner Contest 135 の 問題D (Digits Parade) を解いてみた.
■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 135 解説 を ご覧下さい.
■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 50 51 52 53 54 55 |
// 解き直し. // https://img.atcoder.jp/abc135/editorial.pdf // 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][13]; // 先頭 i 文字まで見て, 13 で割った余りが, j となるもの. int main(){ // 1. 入力情報. char s[101010]; scanf("%s", s); int N = strlen(s); // 2. dp更新. // -> 空文字を, 1通りと数えておく. dp[0][0] = 1; rep(i, N){ // i文字目が, '?'. if(s[i] == '?'){ // 前回, 13 で割った余りが, j だった. rep(j, 13){ // '0' ～ '9' まで試す. rep(k, 10){ // 桁上がりするので, 今回の余りは, 10 * j に 変わるので注意. int r = (10 * j + k) % 13; dp[i + 1][r] += dp[i][j]; dp[i + 1][r] %= MOD; } } } // i文字目が, '?' 以外. if(s[i] != '?'){ // 前回, 13 で割った余りが, j だった. rep(j, 13){ // 桁上がりするので, 今回の余りは, 10 * j に 変わるので注意. int r = (10 * j + (s[i] - '0')) % 13; dp[i + 1][r] += dp[i][j]; dp[i + 1][r] %= MOD; } } } // 3. 出力. printf("%lld\n", dp[N][5]); 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 |
[入力例] ??2??5 [出力例] 768 ※AtCoderテストケースより [入力例] ?44 [出力例] 1 ※AtCoderテストケースより [入力例] 7?4 [出力例] 0 ※AtCoderテストケースより [入力例] ?6?42???8??2??06243????9??3???7258??5??7???????774????4?1??17???9?5?70???76??? [出力例] 153716888 [入力例] 1?? [出力例] 7 [入力例] 8??? [出力例] 77 [入力例] 8?81??5? [出力例] 770 [入力例] 82?25?2503?760185?8??617???15835658?2??55??69762?? [出力例] 763846179 [入力例] 770727717?82808??9252191127251971298727583?17?0269?92731199011800680299961836881090875568506192396795068779998??5658266906993298105838?6215212993530867??8915??7211?996?689272?268952?963316055136811370?7353119560?177725?5880?772?860?9295165577?26008?660701267631371153559915505880883629?139?55553309952?231626768000805?5523169206293?5922?2587?27086?37536268560938053207122?920180623765?29?79391789039?2821?1??727?769?38?807?393?92989?7?371592?53?36271150?9516516013963?297376665763?5176?71673305667722 [出力例] 869231461 |
■参照サイト
AtCoder Beginner Contest 135