C++の練習を兼ねて, AtCoder Regular Contest 056 の 問題C (部門分け) を解いてみた.
■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考にして, AC版に到達できたと思う.
2. 実行時間を改善するため, 過去問(AtCoder Beginner Contest 187 (F – Close Group)) の 解説プログラムを参考に, 一部改変して, 実装した.
3. 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 056 解説 を ご覧下さい.
■C++版プログラム(問題C/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 |
// 解き直し. // https://img.atcoder.jp/data/arc/056/editorial.pdf // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; 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 LL wSum[1 << 17], w[22][22], dp[1 << 17]; int main(){ // 1. 入力情報. int N, K; scanf("%d %d", &N, &K); rep(i, N) rep(j, N) scanf("%lld", &w[i][j]); // 2. 部分集合ごとの重みの総和. rep(i, 1 << N){ vi s; rep(j, N) if(i & (1 << (N - 1 - j))) s.pb(j); for(auto &p : s) for(auto &q : s) wSum[i] += w[p][q]; wSum[i] /= 2; // 重複カウントの除外. } // 3. dp更新. // 以下の実装は, N = 17 で, 5416[ms] などの時間が, かかってしまう(TLE版). /* repx(s, 1, 1 << N){ // 3-1. 部分集合 S の index. vi sIndex; rep(i, N) if(s & (1 << (N - 1 - i))) sIndex.pb(i); // 3-2. dp[S] = dp[S - T] + K - (S - T と T 間 の 辺の重みの総和) を 計算. int l = sIndex.size(); rep(i, 1 << l){ // 部分集合 T. int t = 0; rep(j, l) if(i & (1 << (l - 1 - j))) t += (1 << (N - 1 - sIndex[j])); // dp計算式を実行. dp[s] = max(dp[s], dp[s - t] + K - (wSum[s] - wSum[s - t] - wSum[t])); } } */ // 4. dp更新(修正版). // // 過去問参照(AtCoder Beginner Contest 187 F - Close Group). // https://atcoder.jp/contests/abc187/editorial/488 // https://atcoder.jp/contests/abc187/submissions/19205798 // -> 部分集合 S と T が 同じケースを含めるため, 一部改変(for(int j = i; --j &= i; ) の 部分). // 以下の実装は, N = 17 で, 267[ms] 程度の実行時間 に 改善. repx(s, 1, 1 << N){ for(int t = s; t &= s; t--) dp[s] = max(dp[s], dp[s - t] + K - (wSum[s] - wSum[s - t] - wSum[t])); } // 5. 出力. printf("%lld\n", dp[(1 << N) - 1]); 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 |
[入力例] 3 3 0 1 5 1 0 1 5 1 0 [出力例] 4 ※AtCoderのテストケースより [入力例] 4 8 0 2 3 5 2 0 1 2 3 1 0 8 5 2 8 0 [出力例] 11 ※AtCoderのテストケースより [入力例] 5 10 0 10 1 2 1 10 0 1 2 1 1 1 0 6 7 2 2 6 0 8 1 1 7 8 0 [出力例] 12 ※AtCoderのテストケースより [入力例] 7 23 0 3 6 1 4 3 8 3 0 7 9 9 6 10 6 7 0 10 7 1 10 1 9 10 0 5 3 8 4 9 7 5 0 4 2 3 6 1 3 4 0 5 8 10 10 8 2 5 0 [出力例] 40 [入力例] 10 50 0 5 2 4 8 8 2 9 1 10 5 0 7 1 7 6 10 1 4 2 2 7 0 10 5 3 8 10 5 10 4 1 10 0 10 5 3 3 7 8 8 7 5 10 0 7 6 9 2 9 8 6 3 5 7 0 7 8 3 8 2 10 8 3 6 7 0 10 3 1 9 1 10 3 9 8 10 0 1 8 1 4 5 7 2 3 3 1 0 9 10 2 10 8 9 8 1 8 9 0 [出力例] 235 [入力例] 13 88 0 6 7 3 6 6 9 3 5 9 3 5 8 6 0 7 9 2 10 9 9 5 7 9 1 6 7 7 0 2 6 2 9 8 6 1 5 4 5 3 9 2 0 4 7 8 10 2 2 1 4 10 6 2 6 4 0 10 4 10 6 4 5 10 4 6 10 2 7 10 0 4 7 4 1 3 2 6 9 9 9 8 4 4 0 5 8 1 2 7 1 3 9 8 10 10 7 5 0 7 9 9 5 6 5 5 6 2 6 4 8 7 0 2 4 1 10 9 7 1 2 4 1 1 9 2 0 10 1 10 3 9 5 1 5 3 2 9 4 10 0 8 1 5 1 4 4 10 2 7 5 1 1 8 0 6 8 6 5 10 4 6 1 6 10 10 1 6 0 [出力例] 711 [入力例] 17 59 0 4 5 4 7 1 8 9 10 7 2 2 8 2 5 7 7 4 0 10 8 5 6 1 6 2 5 3 8 10 2 8 10 2 5 10 0 9 6 7 3 2 7 7 10 9 2 8 8 1 6 4 8 9 0 10 2 8 3 9 9 2 2 1 5 2 4 2 7 5 6 10 0 10 3 6 3 9 1 10 4 6 7 2 1 1 6 7 2 10 0 2 5 10 2 6 5 6 9 4 6 9 8 1 3 8 3 2 0 9 9 5 8 3 2 8 8 8 8 9 6 2 3 6 5 9 0 1 8 10 7 5 7 4 3 5 10 2 7 9 3 10 9 1 0 1 1 5 10 2 5 10 2 7 5 7 9 9 2 5 8 1 0 8 8 8 5 7 3 8 2 3 10 2 1 6 8 10 1 8 0 8 8 6 10 4 7 2 8 9 2 10 5 3 7 5 8 8 0 10 1 10 10 9 8 10 2 1 4 6 2 5 10 8 8 10 0 5 7 2 5 2 2 8 5 6 9 8 7 2 5 6 1 5 0 9 9 8 5 8 8 2 7 4 8 4 5 7 10 10 7 9 0 3 10 7 10 1 4 2 6 8 3 10 3 4 10 2 9 3 0 5 7 2 6 2 1 9 8 5 2 8 7 9 5 8 10 5 0 [出力例] 212 |
■参照サイト
AtCoder Regular Contest 056
AtCoder Beginner Contest 187 (F – Close Group)