C++の練習を兼ねて, AtCoder Beginner Contest 184 の 問題F (Programming Contest ) を解いてみた.
■感想.
1. 問題F は, 解答の方針が見えなかったので, 解説を参照して, 実装したところ, ようやくAC版に到達できた.
2. 半分全列挙の復習が出来たので良かったと思う.
3. 個人的には, 非常に面白い問題に感じた.
4. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Beginner Contest 184 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題F／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://atcoder.jp/contests/abc184/editorial/354 // C++(GCC 9.2.1) #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 pb push_back #define all(x) x.begin(), x.end() int main(){ // 1. 入力情報. int N, T; scanf("%d %d", &N, &T); // 2. 要素を, B, C に, 分割保存. int bs = (N - 1) / 2 + 1, cs = N - bs; LL b[bs], c[cs]; rep(i, bs) scanf("%lld", &b[i]); rep(i, cs) scanf("%lld", &c[i]); // 3. B から 選択した場合の あり得る総和. set<LL> bSt; rep(i, 1 << bs){ LL bt = 0; rep(j, bs) if(i & (1 << j)) bt += b[j]; bSt.insert(bt); } vector<LL> v; for(auto &p : bSt) v.pb(p); // 4. C から 選択した場合の あり得る総和を計算しながら, B と 併せて 最大値 を 計算. LL ans = 0; rep(i, 1 << cs){ LL ct = 0; rep(j, cs) if(i & (1 << j)) ct += c[j]; int at = upper_bound(all(v), max(0LL, (LL)T - ct)) - v.begin(); // T分までの残り時間に近い位置を検索. if(at) at--; if(ct + v[at] <= (LL)T) ans = max(ans, ct + v[at]); } // 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 |
[入力例] 5 17 2 3 5 7 11 [出力例] 17 ※AtCoderテストケースより [入力例] 6 100 1 2 7 5 8 10 [出力例] 33 ※AtCoderテストケースより [入力例] 6 100 101 102 103 104 105 106 [出力例] 0 ※AtCoderテストケースより [入力例] 7 273599681 6706927 91566569 89131517 71069699 75200339 98298649 92857057 [出力例] 273555143 ※AtCoderテストケースより [入力例] 12 600 51 59 70 52 76 48 72 84 16 20 110 17 [出力例] 600 ※ 実際, 51 + 70 + 52 + 76 + 48 + 72 + 84 + 20 + 110 + 17 = 600 である. [入力例] 15 700 78 95 25 15 22 74 7 55 56 20 107 15 60 103 73 46 [出力例] 700 ※ 実際, 95 + 25 + 15 + 22 + 74 + 7 + 55 + 56 + 20 + 107 + 15 + 60 + 103 + 46 = 700 である. [入力例] 25 20201208 4890321 4786531 8791932 3771300 7090297 3492295 8049293 7341323 5404897 6316691 7216960 3514956 6211029 8134268 8949965 369535 7715454 2036743 6739359 1621595 4373233 1183789 3241132 2450883 4260007 [出力例] 20200875 ※ 実際, 6316691 + 3514956 + 2036743 + 1621595 + 2450883 + 4260007 = 20200875 |
■参照サイト
AtCoder Beginner Contest 184