C++の練習を兼ねて, AtCoder Regular Contest 017 の 問題C (C – 無駄なものが嫌いな人) を解いてみた.
■感想.
1. 方針が見えなかったので, 解説を参考に, 実装したところ, AC版となった.
2. 半分全列挙というテクニックとのことで, 新しい知識が増えたので良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトARC 017 解説をご覧下さい.
■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 |
// 解き直し. // https://www.slideshare.net/chokudai/arc017 #include <bits/stdc++.h> using namespace std; using LL = long long; #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 a first #define b second LL w[33]; int main(){ // 1. 入力情報. int N; LL X; scanf("%d %lld", &N, &X); rep(i, N) scanf("%lld", &w[i]); // 2. sort. sort(w, w + N); // 3. 解説通り(前半(1 ~ h), 後半(h + 1 ~ N)に分けて, 全探索). // 3-1. 前半部分を計算して, 保存. int h = N / 2; map<LL, LL> fm; rep(i, 1 << h){ LL a = 0; rep(j, h) if(1 & (i >> j)) a += w[j]; fm[a]++; } // 3-2. 後半部分を集計して, 保存. map<LL, LL> lm; rep(i, 1 << (h + (N & 1))){ LL a = 0; rep(j, h + (N & 1)) if(1 & (i >> j)) a += w[j + h]; lm[a]++; } // 4. 集計. LL ans = 0; for(auto i = fm.begin(); i != fm.end(); ++i){ // 後半から, X - p を 探索して, 見つかったら, A * B を 加算. LL xp = X - i->a, A = i->b; if(lm.count(xp) > 0) ans += A * lm[xp]; } // 5. 出力. printf("%lld\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 |
[入力例] 5 5 1 1 2 3 4 [出力例] 4 ※AtCoderのテストケースより [入力例] 8 21 10 4 2 30 22 20 8 14 [出力例] 0 ※AtCoderのテストケースより [入力例] 20 100000000 35576749 38866484 6624951 39706038 11133516 25490903 14701702 17888322 14423251 32111678 24509097 43375049 35298298 21158709 30489274 37977301 19510726 28841291 10293962 12022699 [出力例] 45 ※AtCoderのテストケースより [入力例] 16 8 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 [出力例] 12870 ※AtCoderのテストケースより [入力例] 25 100 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 [出力例] 90888 |
■参照サイト
AtCoder Regular Contest 017