C++の練習を兼ねて, AtCoder Beginner Contest 301 の 問題E (Pac-Takahashi) を解いてみた.
■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 幅優先探索, 苦手な動的計画法(bitDP, 巡回セールスマン問題)の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 301 解説 の 各リンク を ご覧下さい.
■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 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 |
// 解き直し. // https://atcoder.jp/contests/abc301/editorial/6343 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using P = pair<int, int>; using vp = vector<P>; 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 #define a first #define b second const int INF = 1010101010; int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1}; char board[303][303]; int memo[22][22]; int main(){ // 1. 入力情報. int H, W, T; scanf("%d %d %d", &H, &W, &T); rep(i, H){ char c[303]; scanf("%s", c); rep(j, W) board[i][j] = c[j]; } // 2. マス(スタート, お菓子, ゴール)を保存. vp cells; rep(i, H) rep(j, W) if(board[i][j] == 'S') cells.pb({i, j}); rep(i, H) rep(j, W) if(board[i][j] == 'o') cells.pb({i, j}); rep(i, H) rep(j, W) if(board[i][j] == 'G') cells.pb({i, j}); int n = cells.size(); // 3. bfs. // https://ja.wikipedia.org/wiki/幅優先探索 auto bfs = [&](P s, int x) -> void { // 訪問フラグ. int v[303][303]; rep(i, H) rep(j, W) v[i][j] = INF; // 空のキュー. queue<P> q; // 訪問済みフラグ設定. v[s.a][s.b] = 0; // 探索地点 s をキュー q に追加. q.push(s); while(!q.empty()){ // キューから取り出す. P c = q.front(); q.pop(); // 取り出した要素を処理. // x: 列方向, y: 行方向 で考える. rep(i, 4){ int nx = c.b + dx[i]; int ny = c.a + dy[i]; // 訪問不可能なマスは, スキップ. if(nx < 0 || nx >= W || ny < 0 || ny >= H || board[ny][nx] == '#') continue; // 未訪問のマスは, 最短距離を設定. if(v[ny][nx] == INF) v[ny][nx] = v[c.a][c.b] + 1, q.push({ny, nx}); } } // 結果の保存. rep(i, n) memo[x][i] = v[cells[i].a][cells[i].b]; }; // 4. 全探索(指定した二地点間). rep(i, n) bfs(cells[i], i); // 5. bitDP(巡回セールスマン問題). // AtCoder Beginner Contest 180 (E - Traveling Salesman among Aerial Cities) 参照. // https://atcoder.jp/contests/abc180/editorial/154 // スタート(0), お菓子の数(1 ～ n - 2 まで), ゴール(n - 1). // スタートは, フラグ(1) を 立てておく. // ex. // n = 9 // 訪問済マスの部分集合(s) が 10010010G -> 10010011G に変化する場合は, マス 3 or 6 から マス 7 へ 移動と解釈. int ans = -1; int dp[n - 1][1 << (n - 1)]; rep(i, n - 1) rep(j, 1 << (n - 1)) dp[i][j] = INF; dp[0][1 << (n - 2)] = 0; repx(p, 1, n){ // 5-1. (p + 1)個目 の マス を 訪問する場合は？ repx(s, 1 << (n - 2), 1 << (n - 1)){ // 訪問済マスの部分集合が, p個でない場合, Skip. if(__builtin_popcount(s) != p) continue; // 移動元 を マス i とする. rep(i, n - 1){ int bef = 1 << (n - 2 - i); if(s & bef){ // 移動先 を マス j とする. repx(j, 1, n - 1){ int cur = 1 << (n - 2 - j); // 未訪問の場合は, dp更新. if(!(s & cur)) dp[j][s + cur] = min(dp[j][s + cur], dp[i][s] + memo[i][j]); } } } } // 5-2. ゴール に 到着. int d = INF; repx(s, 1 << (n - 2), 1 << (n - 1)){ // 訪問済マスの部分集合が, p個でない場合, Skip. if(__builtin_popcount(s) != p) continue; // ゴール直前のマスを全探索. rep(j, n - 1){ int bef = 1 << (n - 2 - j); if(s & bef) d = min(d, dp[j][s] + memo[j][n - 1]); } } // 5-3. 最大値更新. // -> p は, スタート地点を含むので, 1個少ない値を指定. if(d <= T) ans = p - 1; } // 6. 出力. 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 168 169 170 171 172 173 174 175 176 177 |
[入力例] 3 3 5 S.G o#o .#. [出力例] 1 ※AtCoderテストケースより [入力例] 3 3 1 S.G .#o o#. [出力例] -1 ※AtCoderテストケースより [入力例] 5 10 2000000 S.o..ooo.. ..o..o.o.. ..o..ooo.. ..o..o.o.. ..o..ooo.G [出力例] 18 ※AtCoderテストケースより [入力例] 12 10 15 ......o.#. ##..#..... .#..o..#.. .o........ ..#...o#.. ..S....#.. ....o..... #.#....#.. ......o... ..#....#.. ....G.o... ..#..#..#. [出力例] 4 [入力例] 16 30 123 ....#..............o.......G.. ...o#..######................. .............######....#...... #####........o....#....#...... .............#....#......o.... ......#.#....#.........#.#.#.. ......#.o.#................#.. ........#.........#........#.. ..........#.......#....#...#.. ..........#............#...... ..........#............#...... ..........#............#...... ###.#.....#............#...... ...o#.....#............#...... ....#.....#............#.#.... ....#....S#............#.o.... [出力例] 7 [入力例] 100 100 2023 .................................................................................................... ...........o........................................................................................ #################################################################################################.## .................................#.o.#.............................................................. ....S............................#...#....................................#...#..................... ..........................................................................#.o.#..................... #################################################################################################.## .................................................................................................... .................................................................................................... #############.##################################.######################################.############ .............................#...................................................................... #################################################################################################.## .............................#............................................#......................... .............................#...................o........................#......................... ................o............#............................................#......................... ..........................................................................#......................... #########.###################################################.#####################################. .................................................................................................... ......#######....................................................................................... ......#.....#....................................................................................... ......#..o..#................................................................................o...... ......#.....#....................................................................................... ......#.....#....................................................................................... .................................................................................................... ###.#########################################.#################################.#################### .................................................................................................... .................................................................................................... #################################################################################################.## .................................................................................................... .................................................................................................... ###############################################.#################################################### .................................................................................................... .................................................................................................... #################################################################################################.## .................................................................................................... .................................................................................................... ##.################################################################################################# .................................................................................................... .................................................................................................... #################################################################################################.## .................................................................................................... .................................................................................................... ##.################################################################################################# .....................................................................o.............................. .................................................................................................... ..................................o................................................................. .................................................................................................... #################################################################################################.## .................................................................................................... .................................................................................................... ##.################################################################################################# .................................................................................................... .................................................................................................... ..................................................................#######..................#...#.... .................###..#...........................................#..o..#..................#.o.#.... .................#....#...........................................#.....#..................#####.... .................#.o..#............................................................................. #################################################################################################.## .................................................................................................... .................................................................................................... ##.################################################################################################# ............................................#o...................................................... ............................................##...................................................... .................................................................................................... #################################################################################################.## ....................#............................................................................... ................#o.................................................................................. ##.################################################################################################# .......................................................................................#.o..#....... .......................................................................................#....#....... .......................................................................................#....#....... .......................................................................................###..#....... .................................................................................................... .................................................................................................... #################################################################################################.## .................................................................................................... ###.################################################################################################ .................................................................................................... .............................................................................##.#................... .............................................................................#..#................... .............................................................................#.o#................... .............................................................................#..#................... ##.################################################################################################# .................................................................................................... .................................................................................................... .................................................................................................... .####............................................................................................... .#.o#............................................................................................... .#..#............................................................................................... ....#............................................#.................................................. #################################################################################################.## ...........................#........#........#...................................................... ..................................#................................................................. ..........................#....#.........#.......#.................................................. ##.################################################################################################# ..................#............................................................................G.... ........#....#............#......................................................................... #################################################################################################.## ............................o..#....#.......#.......##........###................................... ...........................###........#.........##.......###........................................ [出力例] 15 |
■参照サイト
パナソニックグループプログラミングコンテスト2023（AtCoder Beginner Contest 301）