C++の練習を兼ねて, AtCoder Beginner Contest 142 の 問題E (Get Everything) を解いてみた.
■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. 最初, TLE版で実装したが, 計算量の削減方法が分からず, dp更新式に渡す鍵情報を, AtCoder Beginner Contest 142 (解説プログラム)を参考に修正している.
4. 個人的には, 動的計画法に関する理解を, 深めることが出来たように感じた.
現状, TLE版 と AC版 との違いは, 本質的には, 鍵情報の捉え方の違いにあると理解している.
→ 具体的には, 鍵情報が, {宝箱1, 宝箱2, 宝箱3} だった場合に, TLE版では, {宝箱1}, {宝箱2}, {宝箱3}, {宝箱1, 宝箱2}, {宝箱1, 宝箱3}, {宝箱2, 宝箱3}, {宝箱1, 宝箱2, 宝箱3} の 7通りの鍵情報で, dp更新を行っているが, AC版では, {宝箱1, 宝箱2, 宝箱3} の 1通りの鍵情報で, dp計算を行っているため, 計算量に違いが現れたと理解している.
→ さらに, TLE版 と AC版 は, dp配列 の 途中部分は, 差分が生じるものの, 最終的に必要な情報は, すべての宝箱を, 開けることが出来るかどうか(および, 最小費用)であるため, 各鍵毎に, 常に, 1通りの鍵情報(ここでは, {宝箱1, 宝箱2, 宝箱3})を見れば十分という点について, なるほどと, 改めて感じた.
5. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 142 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題E／TLE版).
|
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 |
// 解き直し. // https://img.atcoder.jp/abc142/editorial.pdf // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using vi = vector<int>; #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 pb push_back int dp[1010][1 << 12]; int main(){ // 1. 入力情報. int N, M; scanf("%d %d", &N, &M); // 2. 初期化. rep(i, 1010) rep(j, 1 << N) dp[i][j] = 2020202020; dp[0][0] = 0; // 3. dp更新. rep(i, M){ // i個目の鍵情報. // ex. // 鍵 1, 3, 7 が 手に入った場合, // 集合 {1}, {3}, {7}, {1, 3}, {1, 7}, {3, 7}, {1, 3, 7} の 組み合わせで, 見る必要があることに注意. int t[1 << N]; rep(j, 1 << N) t[j] = 0; t[0] = 1; int a, b, c; scanf("%d %d", &a, &b); rep(j, b){ scanf("%d", &c); repr(j, (1 << N) - 1, 0) if(t[j]) t[j + (1 << (N - c))] = 1; } // 鍵情報の組み合わせ保存. vi key; repx(j, 1, 1 << N) if(t[j]) key.pb(j); // for(auto &k : key) printf("%d ", k); // puts("\n----------"); // 前回分反映. rep(j, 1 << N) dp[i + 1][j] = dp[i][j]; // 宝箱を開けるための最小コスト. // -> 状態 j は, 開いている宝箱情報と見る. // ex. // N = 12 で, j = 100010100011 は, 宝箱 = {1, 2, 6, 8, 12} が 開いていると見る. rep(j, 1 << N) for(auto &k : key) dp[i + 1][j | k] = min({dp[i + 1][j | k], dp[i][j | k], dp[i][j] + a}); // rep(j, 1 << N) printf("%d ", dp[i + 1][j]); // puts("\n----------"); } // 4. 集計. int ans = dp[M][(1 << N) - 1]; if(ans == 2020202020) ans = -1; // 5. 出力. printf("%d\n", ans); return 0; } |
■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 |
// 解き直し. // https://img.atcoder.jp/abc142/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--) int dp[1010][1 << 12]; int main(){ // 1. 入力情報. int N, M; scanf("%d %d", &N, &M); // 2. 初期化. rep(i, 1010) rep(j, 1 << N) dp[i][j] = 2020202020; dp[0][0] = 0; // 3. dp更新(01-handmade-07 で, TLE版だったため, ロジック修正). rep(i, M){ // i個目の鍵情報. // -> 状態 j は, 開いている宝箱情報と見る. // ex. // N = 12 で, j = 100010100011 は, 宝箱 = {1, 2, 6, 8, 12} が 開いていると見る. int a, b, c, key = 0; scanf("%d %d", &a, &b); rep(j, b){ scanf("%d", &c); key |= (1 << (N - c)); } // 前回分反映. rep(j, 1 << N) dp[i + 1][j] = dp[i][j]; // 宝箱を開けるための最小コスト. rep(j, 1 << N) dp[i + 1][j | key] = min({dp[i + 1][j | key], dp[i][j | key], dp[i][j] + a}); } // 4. 集計. int ans = dp[M][(1 << N) - 1]; if(ans == 2020202020) ans = -1; // 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 |
[入力例] 2 3 10 1 1 15 1 2 30 2 1 2 [出力例] 25 ※AtCoderテストケースより [入力例] 12 1 100000 1 2 [出力例] -1 ※AtCoderテストケースより [入力例] 4 6 67786 3 1 3 4 3497 1 2 44908 3 2 3 4 2156 3 2 3 4 26230 1 2 86918 1 3 [出力例] 69942 ※AtCoderテストケースより [入力例] 5 7 83 3 1 2 3 93 1 4 10 1 1 114 2 2 5 119 1 3 84 2 4 5 17 2 2 5 [出力例] 167 [入力例] 12 15 13483 2 1 5 5458 1 6 10474 6 2 3 7 8 10 11 3974 3 9 11 12 11592 3 1 2 3 12856 3 4 5 6 3538 4 7 8 9 10 2999 1 11 3780 3 1 11 12 9159 2 5 6 2890 3 7 9 10 11778 4 3 5 8 9 11169 5 1 2 5 7 11 12798 5 3 4 7 8 9 9578 1 2 [出力例] 30000 |
■参照サイト
AtCoder Beginner Contest 142
AtCoder Beginner Contest 142 (解説プログラム)