C++の練習を兼ねて, AtCoder Beginner Contest 037 の 問題D (経路) を解いてみた.
■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考に, AC版に到達できた.
2. 本問は, メモ化再帰の例題として, 学習した内容である.
相変わらず, メモ化再帰の本質が見えてないため, 理解が進むまでは, 本問を, 典型的な例題として, いったん丸暗記の方針とした.
とはいえ, メモ化再帰は, 以下の構成要素(ロジック)が含まれていると, とりあえず理解した.
① 第一段階 … メモ化が終わっているか確認する作業, 再帰処理の終了条件として使用する.
② 第二段階 … 再帰処理の実装, 本問では, “経路数” を知りたいので, 経路数 を 集計する実装が必要.
③ 第三段階 … メモ化が終わってないため, メモ化の作業を追加, なお, 本問では, メモ化の対象は, “経路数” と 理解.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 037 解説 を ご覧下さい.
■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 56 57 58 59 60 |
// 解き直し. // https://img.atcoder.jp/data/abc/037/editorial.pdf // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using vl = vector<LL>; using vvl = vector<vl>; #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--) constexpr int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1}; const LL MOD = 1e9 + 7; int main(){ // 1. 入力情報. int H, W; scanf("%d %d", &H, &W); vvl a(H, vl(W)); rep(i, H) rep(j, W) scanf("%lld", &a[i][j]); // 2. dfs. // https://ja.wikipedia.org/wiki/深さ優先探索 vvl dp(H, vl(W)); auto dfs = [&](auto self, int hCur, int wCur) -> LL{ // 2-1. 終了条件. // -> 前回以前に, メモ化が完了しているため終了. if(dp[hCur][wCur]) return dp[hCur][wCur]; // 2-2. 経路数 f(i, j) の 計算. LL ret = 1; rep(i, 4){ // 移動先候補. int hNex = hCur + dy[i]; int wNex = wCur + dx[i]; // 移動不可能. if(wNex < 0 || wNex >= W || hNex < 0 || hNex >= H) continue; // 移動可能. if(a[hCur][wCur] < a[hNex][wNex]) ret = (ret + self(self, hNex, wNex)) % MOD; } // 2-3. メモ化. // -> まだ, メモ化していないマスに対して, メモ化する. // ここで, 本問でのメモ化対象は, 解説にある f(i, j) を dp[i][j] に保存(メモ化)すると理解. return dp[hCur][wCur] = ret; }; // 3. 集計. LL ans = 0; rep(i, H) rep(j, W) ans = (ans + dfs(dfs, i, j)) % MOD; // 4. 出力. 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 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 87 88 |
[入力例] 2 3 1 4 5 2 4 9 [出力例] 18 ※AtCoderテストケースより [入力例] 6 6 1 3 4 6 7 5 1 2 4 8 8 7 2 7 9 2 7 2 9 4 2 7 6 5 2 8 4 6 7 6 3 7 9 1 2 7 [出力例] 170 ※AtCoderテストケースより [入力例] 3 3 1 2 3 6 5 4 7 8 9 [出力例] 77 [入力例] 20 10 6 44 80 52 78 83 4 44 83 71 62 78 40 65 94 29 59 74 23 116 75 14 103 67 18 7 15 73 116 12 44 14 64 103 9 3 122 40 91 12 96 48 71 14 87 13 41 57 29 88 112 39 39 53 108 69 18 8 113 22 85 37 9 48 4 34 101 119 28 12 51 35 30 28 76 51 107 106 20 121 49 118 9 67 89 92 54 97 123 32 68 83 37 102 119 54 67 60 2 64 105 72 81 107 50 92 51 30 30 78 122 32 20 3 33 42 112 45 14 118 108 13 64 33 49 82 104 63 115 115 36 96 83 57 120 58 23 54 77 41 120 47 113 34 100 99 84 79 70 12 4 114 98 118 104 116 78 14 5 121 46 8 97 64 68 117 115 90 57 120 13 117 23 106 27 23 11 74 57 73 86 75 80 6 115 75 79 36 45 59 13 66 103 28 89 92 54 114 114 9 [出力例] 1335 [入力例] 25 30 111 59 96 84 98 107 13 25 75 36 8 14 13 115 29 24 37 5 75 100 2 100 101 81 24 9 4 90 120 26 35 21 47 111 103 69 95 40 34 17 8 82 34 75 34 90 30 103 16 22 84 71 49 13 30 26 47 9 60 34 43 4 36 64 60 114 37 121 77 102 38 123 77 121 86 22 43 80 76 30 89 57 60 7 40 11 7 96 66 55 2 73 105 40 45 90 89 37 8 113 10 102 47 109 82 114 19 52 55 72 39 57 53 70 122 83 4 23 38 46 72 66 110 28 39 101 63 59 68 82 110 65 9 106 118 115 122 102 42 3 71 43 114 20 81 97 71 113 51 39 62 62 104 45 1 23 23 36 66 63 76 3 24 109 68 70 66 38 85 68 21 98 74 118 107 60 117 11 40 117 84 52 61 30 122 92 50 87 94 114 108 52 91 48 97 31 120 67 67 93 55 33 17 70 22 15 30 95 36 93 43 66 117 31 8 11 53 47 69 13 110 51 118 117 92 2 84 119 18 34 18 34 16 86 55 103 52 51 47 92 41 36 106 70 93 108 41 117 119 120 89 85 37 7 123 55 69 44 112 30 77 76 67 25 63 40 89 107 111 22 18 6 25 9 55 69 120 24 14 92 58 64 109 84 113 68 46 103 56 105 13 108 8 29 36 31 58 115 30 5 119 54 98 77 96 46 39 59 65 77 77 105 20 20 79 13 83 78 66 5 31 27 43 60 102 5 23 119 55 23 52 46 84 105 15 105 92 81 32 70 25 17 58 70 17 102 115 85 65 37 59 92 66 80 90 22 5 15 45 89 22 65 43 58 105 40 33 29 113 37 59 53 81 113 116 88 51 20 42 82 32 5 91 3 99 98 11 97 99 72 106 2 87 16 38 55 118 63 30 68 9 57 114 36 102 40 110 46 42 3 72 116 104 98 51 59 95 3 10 25 110 117 103 18 32 78 2 42 49 111 51 40 121 18 34 5 32 87 1 64 81 43 45 106 69 36 100 68 77 38 27 37 121 44 93 89 79 62 120 64 56 70 47 101 96 102 50 119 117 112 108 95 109 85 110 104 91 121 9 2 93 83 30 98 92 36 92 90 88 25 5 23 27 116 72 76 71 17 20 67 94 83 100 56 77 26 66 23 90 58 46 51 5 115 11 21 52 38 28 4 113 27 44 72 32 39 19 11 38 38 99 3 46 52 14 22 47 68 31 13 46 118 103 11 14 79 77 113 90 99 33 87 54 96 90 92 35 1 89 16 36 109 38 65 81 25 34 8 50 24 34 45 10 44 23 103 57 96 86 122 37 84 33 64 85 41 59 38 105 55 45 10 32 87 107 106 10 2 84 42 53 8 23 34 73 77 24 39 10 91 18 58 85 88 112 44 38 64 58 69 72 57 101 39 51 86 32 85 40 91 17 11 6 88 26 31 79 91 106 4 23 64 5 78 48 108 89 95 59 64 33 80 33 73 12 30 52 78 96 109 72 10 120 18 42 4 36 48 16 45 40 58 52 28 74 49 85 15 123 33 114 12 52 65 6 105 86 62 38 49 5 86 76 106 22 28 111 78 8 33 73 14 116 84 85 113 54 99 80 37 4 91 123 85 120 3 114 79 66 98 52 76 26 102 32 28 54 37 60 104 9 104 47 20 90 25 29 53 84 22 3 122 121 109 72 3 5 76 31 58 [出力例] 5185 |
■参照サイト
AtCoder Beginner Contest 037