C++の練習を兼ねて, AtCoder Beginner Contest 008 の 問題D (金塊ゲーム) を解いてみた.
■感想.
1. 問題D は, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 苦手な動的計画法 の訓練が積めたので, 非常に良かったと思う.
3. メモ化再帰 の 復習もできたので, 非常に良かったと思う.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 008 解説 の 各リンク を ご覧下さい.
■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 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 |
// 解き直し. // https://img.atcoder.jp/abc008/editorial.pdf // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; #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--) #define a first #define b second int dp[101][101][101][101], x[33], y[33]; int main(){ // 1. 入力情報. int W, H, N; scanf("%d %d %d", &W, &H, &N); map<int, int> mxi, mxo, myi, myo; mxi[1] = myi[1] = mxi[W] = myi[H] = 0; rep(i, N){ scanf("%d %d", &x[i], &y[i]); mxi[x[i]] = myi[y[i]] = 0; if(x[i] > 1) mxi[x[i] - 1] = 0; if(y[i] > 1) myi[y[i] - 1] = 0; if(x[i] < W) mxi[x[i] + 1] = 0; if(y[i] < H) myi[y[i] + 1] = 0; } // 2. 座標圧縮. int idx = -1; for(auto &p : mxi) p.b = ++idx; for(auto &p : mxi) mxo[p.b] = p.a; int idy = -1; for(auto &p : myi) p.b = ++idy; for(auto &p : myi) myo[p.b] = p.a; // 3. dfs. // https://ja.wikipedia.org/wiki/深さ優先探索 auto dfs = [&](auto&& self, int x1, int y1, int x2, int y2) -> int { // 終了条件. if(dp[x1][y1][x2][y2] != -1) return dp[x1][y1][x2][y2]; // 再帰処理(各クレーン). int ret = 0; rep(i, N){ // 回収可能か? if(mxi[x[i]] < x1 || mxi[x[i]] > x2 || myi[y[i]] < y1 || myi[y[i]] > y2) continue; // 金塊の回収. // クレーン. int cur = (mxo[x2] - mxo[x1]) + (myo[y2] - myo[y1]) + 1; // 左. if(x[i] > 1){ // 左下. if(y[i] > 1) cur += self(self, x1, y1, mxi[x[i] - 1], myi[y[i] - 1]); // 左上. if(y[i] < H) cur += self(self, x1, myi[y[i] + 1], mxi[x[i] - 1], y2); } // 右. if(x[i] < W){ // 右下. if(y[i] > 1) cur += self(self, mxi[x[i] + 1], y1, x2, myi[y[i] - 1]); // 右上. if(y[i] < H) cur += self(self, mxi[x[i] + 1], myi[y[i] + 1], x2, y2); } // 最大値更新. ret = max(ret, cur); } // メモ化して返却. return (dp[x1][y1][x2][y2] = ret); }; // 4. dp更新. rep(i, 101) rep(j, 101) rep(k, 101) rep(l, 101) dp[i][j][k][l] = -1; int ans = dfs(dfs, mxi[1], myi[1], mxi[W], myi[H]); // 5. 出力. printf("%d\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 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 |
[入力例] 6 4 3 2 4 3 1 4 3 [出力例] 19 ※AtCoderテストケースより [入力例] 3 3 3 1 1 2 3 3 2 [出力例] 9 ※AtCoderテストケースより [入力例] 15 10 8 7 10 12 8 4 4 5 7 9 9 1 6 6 5 3 2 [出力例] 112 ※AtCoderテストケースより [入力例] 10 15 10 3 12 10 1 8 11 6 11 4 10 1 3 5 10 4 11 5 9 3 4 [出力例] 102 [入力例] 333 333 15 104 52 7 204 13 81 2 170 66 149 315 21 291 195 29 333 330 317 29 128 331 236 95 167 172 187 295 252 121 239 [出力例] 6230 [入力例] 35 30 20 20 28 13 28 15 19 17 23 24 2 1 20 3 13 30 13 18 10 13 13 18 11 29 29 6 10 22 20 30 25 24 30 2 29 35 9 32 9 24 8 [出力例] 512 [入力例] 500 500 20 21 175 490 480 256 191 391 387 9 418 96 153 458 325 167 259 84 110 84 243 237 259 353 71 332 190 399 61 167 23 37 206 217 460 269 12 89 173 100 410 [出力例] 10682 [入力例] 1000000 1000000 30 637828 319816 244524 123531 562573 809275 720223 918249 883753 853155 141958 383641 964471 19449 244552 25727 877562 368658 198190 576776 807178 858672 723437 434181 118576 250190 650166 872144 559030 352602 211905 971770 170666 972127 950292 367351 69139 404753 956204 162668 35771 168055 940217 706249 914198 373742 378983 854296 49242 132854 756632 863851 974092 503954 975854 274858 95497 890691 365021 25373 [出力例] 32383224 |
■参照サイト
AtCoder Beginner Contest 008