C++の練習を兼ねて, AtCoder Beginner Contest 147 の 問題E (Balanced Path) を解いてみた.
■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に, AC版に到達できた.
2. 苦手な動的計画法の訓練を積めたこと, および, bitsetの使い方を訓練できたのが非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 147 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題E／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 |
// 説き直し. // https://img.atcoder.jp/abc147/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 all(x) x.begin(), x.end() int a[101][101], b[101][101]; int main(){ // 1. 入力情報. int H, W; scanf("%d %d", &H, &W); rep(i, H) rep(j, W) scanf("%d", &a[i + 1][j + 1]); rep(i, H) rep(j, W) scanf("%d", &b[i + 1][j + 1]); // 2. dp更新. bitset<50505> dp[H + 2][W + 2]; dp[1][1][25000 + abs(a[1][1] - b[1][1])] = true; rep(k, H + W + 1){ rep(i, min(k + 1, H + 1)){ int j = k - i; if(!i || !j) continue; if(i > H) continue; if(j > W) continue; // 今回分取得. bitset<50505> dp00 = dp[i][j]; bitset<50505> dp01 = dp[i][j]; bitset<50505> dp10 = dp[i][j]; bitset<50505> dp11 = dp[i][j]; // マス(i, j) -> マス(i + 1, j). dp[i + 1][j] |= (dp00 <<= abs(a[i + 1][j] - b[i + 1][j])); dp[i + 1][j] |= (dp01 >>= abs(a[i + 1][j] - b[i + 1][j])); // マス(i, j) -> マス(i, j + 1). dp[i][j + 1] |= (dp10 <<= abs(a[i][j + 1] - b[i][j + 1])); dp[i][j + 1] |= (dp11 >>= abs(a[i][j + 1] - b[i][j + 1])); } } // 3. 文字列化. string dpStr = dp[H][W].to_string(); reverse(all(dpStr)); // 4. 偏りの最小値は？ // 4-1. 右側. int ans = 202020; repx(i, 25000, dpStr.size()){ if(dpStr[i] == '1'){ ans = min(ans, i - 25000); break; } } // 4-2. 左側. repr(i, 25000, 0){ if(dpStr[i] == '1'){ ans = min(ans, 25000 - i); break; } } // 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 |
[入力例] 2 2 1 2 3 4 3 4 2 1 [出力例] 0 ※AtCoderテストケースより [入力例] 2 3 1 10 80 80 10 1 1 2 3 4 5 6 [出力例] 2 ※AtCoderテストケースより [入力例] 2 2 1 5 7 11 3 8 21 25 [出力例] 2 [入力例] 3 3 76 5 11 7 0 35 39 45 7 3 39 1 0 15 47 7 77 2 [出力例] 3 [入力例] 3 5 8 12 9 7 0 8 10 14 6 10 0 17 18 8 3 5 18 12 2 6 11 9 1 10 18 1 10 17 12 1 [出力例] 0 |
■参照サイト
AtCoder Beginner Contest 147