C++の練習を兼ねて, AtCoder Beginner Contest 180 の 問題E (Traveling Salesman among Aerial Cities) を解いてみた.
■感想.
1. 問題Eは, 方針が見えず, 解説を参照して実装し, ようやく, AC版となった.
2. 苦手なdpの訓練(本問では, bitDP)を積めたので, 非常に良かったと思う.
3. 個人的には, 非常に面白い問題に感じた.
4. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Beginner Contest 180 解説 の 各リンク を ご覧下さい.
■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 |
// 解き直し. // https://atcoder.jp/contests/abc180/editorial/154 // 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 pb push_back int x[22], y[22], z[22]; // 各都市 の 座標. int cost[22][22]; // 都市 i -> 都市 j の 移動コスト. int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N) scanf("%d %d %d", &x[i], &y[i], &z[i]); // 2. 都市 i -> 都市 j の 移動コスト. rep(i, N) rep(j, N) cost[i][j] = abs(x[j] - x[i]) + abs(y[j] - y[i]) + max(0, z[j] - z[i]); // 3. dp更新. // ex. // N = 6 // s が 101001 -> 111001 に変化する場合は, 都市 3 から 都市 2 へ 移動と解釈. int dp[N][1 << N]; rep(i, N) rep(j, 1 << N) dp[i][j] = 1010101010; dp[0][1 << (N - 1)] = 0; repx(p, 1, N){ // 3-1. (p + 1)個目 の 街 を 訪問する場合は？ repx(s, 1 << (N - 1), 1 << N){ // 3-2. 訪問済 の 街の集合が, p個である場合. if(__builtin_popcount(s) == p){ // 3-3. 移動元 を 都市 i とする. rep(i, N){ int bef = 1 << (N - 1 - i); if(s & bef){ // 3-4. 移動先 を 都市 j とし, dp更新. repx(j, 1, N){ int cur = 1 << (N - 1 - j); if(!(s & cur)) dp[j][s + cur] = min(dp[j][s + cur], dp[i][s] + cost[i][j]); } } } } } } // 4. 都市 1 に 戻る. int ans = 1010101010; repx(i, 1, N) ans = min(ans, dp[i][(1 << N) - 1] + cost[i][0]); // 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 |
[入力例] 2 0 0 0 1 2 3 [出力例] 9 ※AtCoderテストケースより [入力例] 3 0 0 0 1 1 1 -1 -1 -1 [出力例] 10 ※AtCoderテストケースより [入力例] 17 14142 13562 373095 -17320 508075 68877 223606 -79774 9979 -24494 -89742 783178 26457 513110 -64591 -282842 7124 -74619 31622 -77660 -168379 -33166 -24790 -3554 346410 16151 37755 -36055 51275 463989 37416 -573867 73941 -3872 -983346 207417 412310 56256 -17661 -42426 40687 -119285 43588 -989435 -40674 -447213 -59549 -99579 45825 7569 45584 [出力例] 6519344 ※AtCoderテストケースより [入力例] 5 161 560 -133 307 -274 246 21 450 -547 -25 561 444 160 -553 82 [出力例] 4105 [入力例] 13 816401 -335930 196982 516442 540869 757047 762652 -360494 858741 62175 -164846 282668 807559 272001 -72863 929055 824663 -153815 -438363 100290 981822 -256837 502105 100612 144931 716832 809205 -300099 -374150 679054 42820 76514 -739391 691879 260849 -507805 250553 -45231 143330 [出力例] 10100563 |
■参照サイト
AtCoder Beginner Contest 180